src/backend/access/gist/gist.c

   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.63 2000/10/21 15:43:09 vadim Exp $
  10  *
  11  *-------------------------------------------------------------------------
  12  */
  13
  14 #include "postgres.h"
  15
  16 #include "access/genam.h"
  17 #include "access/gist.h"
  18 #include "access/gistscan.h"
  19 #include "access/heapam.h"
  20 #include "catalog/index.h"
  21 #include "catalog/pg_index.h"
  22 #include "executor/executor.h"
  23 #include "miscadmin.h"
  24 #include "utils/syscache.h"
  25
  26 #ifdef XLOG
  27 #include "access/xlogutils.h"
  28 void gist_redo(XLogRecPtr lsn, XLogRecord *record);
  29 void gist_undo(XLogRecPtr lsn, XLogRecord *record);
  30 void gist_desc(char *buf, uint8 xl_info, char* rec);
  31 #endif
  32
  33 /* non-export function prototypes */
  34 static InsertIndexResult gistdoinsert(Relation r, IndexTuple itup,
  35                          GISTSTATE *GISTstate);
  36 static InsertIndexResult gistentryinsert(Relation r, GISTSTACK *stk,
  37                                 IndexTuple tup,
  38                                 GISTSTATE *giststate);
  39 static void gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
  40                                    IndexTuple rtup, GISTSTATE *giststate);
  41 static void gistAdjustKeys(Relation r, GISTSTACK *stk, BlockNumber blk,
  42                            char *datum, int att_size, GISTSTATE *giststate);
  43 static void gistintinsert(Relation r, GISTSTACK *stk, IndexTuple ltup,
  44                           IndexTuple rtup, GISTSTATE *giststate);
  45 static InsertIndexResult gistSplit(Relation r, Buffer buffer,
  46                   GISTSTACK *stack, IndexTuple itup,
  47                   GISTSTATE *giststate);
  48 static void gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt,
  49                         IndexTuple rt);
  50 static void GISTInitBuffer(Buffer b, uint32 f);
  51 static BlockNumber gistChooseSubtree(Relation r, IndexTuple itup, int level,
  52                                   GISTSTATE *giststate,
  53                                   GISTSTACK **retstack, Buffer *leafbuf);
  54 static OffsetNumber gistchoose(Relation r, Page p, IndexTuple it,
  55                    GISTSTATE *giststate);
  56 static int      gistnospace(Page p, IndexTuple it);
  57 static IndexTuple gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t);
  58 static void gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr,
  59                            Relation r, Page pg, OffsetNumber o, int b, bool l);
  60
  61 #ifdef GISTDEBUG
  62 static char *int_range_out(INTRANGE *r);
  63
  64 #endif
  65
  66 /*
  67 ** routine to build an index.  Basically calls insert over and over
  68 */
  69 Datum
  70 gistbuild(PG_FUNCTION_ARGS)
  71 {
  72         Relation                heap = (Relation) PG_GETARG_POINTER(0);
  73         Relation                index = (Relation) PG_GETARG_POINTER(1);
  74         IndexInfo          *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
  75         Node               *oldPred = (Node *) PG_GETARG_POINTER(3);
  76 #ifdef NOT_USED
  77         IndexStrategy   istrat = (IndexStrategy) PG_GETARG_POINTER(4);
  78 #endif
  79         HeapScanDesc hscan;
  80         HeapTuple       htup;
  81         IndexTuple      itup;
  82         TupleDesc       htupdesc,
  83                                 itupdesc;
  84         Datum           attdata[INDEX_MAX_KEYS];
  85         char            nulls[INDEX_MAX_KEYS];
  86         int                     nhtups,
  87                                 nitups;
  88         Node       *pred = indexInfo->ii_Predicate;
  89 #ifndef OMIT_PARTIAL_INDEX
  90         TupleTable      tupleTable;
  91         TupleTableSlot *slot;
  92 #endif
  93         ExprContext *econtext;
  94         InsertIndexResult res = NULL;
  95         GISTSTATE       giststate;
  96         GISTENTRY       tmpcentry;
  97         Buffer          buffer = InvalidBuffer;
  98         bool       *compvec;
  99         int                     i;
 100
 101         /* no locking is needed */
 102
 103         initGISTstate(&giststate, index);
 104
 105         /*
 106          * We expect to be called exactly once for any index relation. If
 107          * that's not the case, big trouble's what we have.
 108          */
 109         if (oldPred == NULL && RelationGetNumberOfBlocks(index) != 0)
 110                 elog(ERROR, "%s already contains data", RelationGetRelationName(index));
 111
 112         /* initialize the root page (if this is a new index) */
 113         if (oldPred == NULL)
 114         {
 115                 buffer = ReadBuffer(index, P_NEW);
 116                 GISTInitBuffer(buffer, F_LEAF);
 117                 WriteBuffer(buffer);
 118         }
 119
 120         /* get tuple descriptors for heap and index relations */
 121         htupdesc = RelationGetDescr(heap);
 122         itupdesc = RelationGetDescr(index);
 123
 124         /*
 125          * If this is a predicate (partial) index, we will need to evaluate
 126          * the predicate using ExecQual, which requires the current tuple to
 127          * be in a slot of a TupleTable.  In addition, ExecQual must have an
 128          * ExprContext referring to that slot.  Here, we initialize dummy
 129          * TupleTable and ExprContext objects for this purpose. --Nels, Feb 92
 130          *
 131          * We construct the ExprContext anyway since we need a per-tuple
 132          * temporary memory context for function evaluation -- tgl July 00
 133          */
 134 #ifndef OMIT_PARTIAL_INDEX
 135         if (pred != NULL || oldPred != NULL)
 136         {
 137                 tupleTable = ExecCreateTupleTable(1);
 138                 slot = ExecAllocTableSlot(tupleTable);
 139                 ExecSetSlotDescriptor(slot, htupdesc);
 140         }
 141         else
 142         {
 143                 tupleTable = NULL;
 144                 slot = NULL;
 145         }
 146         econtext = MakeExprContext(slot, TransactionCommandContext);
 147 #else
 148         econtext = MakeExprContext(NULL, TransactionCommandContext);
 149 #endif   /* OMIT_PARTIAL_INDEX */
 150
 151         /* build the index */
 152         nhtups = nitups = 0;
 153
 154         compvec = (bool *) palloc(sizeof(bool) * indexInfo->ii_NumIndexAttrs);
 155
 156         /* start a heap scan */
 157         hscan = heap_beginscan(heap, 0, SnapshotNow, 0, (ScanKey) NULL);
 158
 159         while (HeapTupleIsValid(htup = heap_getnext(hscan, 0)))
 160         {
 161                 MemoryContextReset(econtext->ecxt_per_tuple_memory);
 162
 163                 nhtups++;
 164
 165 #ifndef OMIT_PARTIAL_INDEX
 166                 /*
 167                  * If oldPred != NULL, this is an EXTEND INDEX command, so skip
 168                  * this tuple if it was already in the existing partial index
 169                  */
 170                 if (oldPred != NULL)
 171                 {
 172                         slot->val = htup;
 173                         if (ExecQual((List *) oldPred, econtext, false))
 174                         {
 175                                 nitups++;
 176                                 continue;
 177                         }
 178                 }
 179
 180                 /*
 181                  * Skip this tuple if it doesn't satisfy the partial-index
 182                  * predicate
 183                  */
 184                 if (pred != NULL)
 185                 {
 186                         slot->val = htup;
 187                         if (!ExecQual((List *) pred, econtext, false))
 188                                 continue;
 189                 }
 190 #endif   /* OMIT_PARTIAL_INDEX */
 191
 192                 nitups++;
 193
 194                 /*
 195                  * For the current heap tuple, extract all the attributes we use
 196                  * in this index, and note which are null.
 197                  */
 198                 FormIndexDatum(indexInfo,
 199                                            htup,
 200                                            htupdesc,
 201                                            econtext->ecxt_per_tuple_memory,
 202                                            attdata,
 203                                            nulls);
 204
 205                 /* immediately compress keys to normalize */
 206                 for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
 207                 {
 208                         gistcentryinit(&giststate, &tmpcentry, (char *) attdata[i],
 209                                                    (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
 210                                                    -1 /* size is currently bogus */ , TRUE);
 211                         if (attdata[i] != (Datum) tmpcentry.pred &&
 212                                 !(giststate.keytypbyval))
 213                                 compvec[i] = TRUE;
 214                         else
 215                                 compvec[i] = FALSE;
 216                         attdata[i] = (Datum) tmpcentry.pred;
 217                 }
 218
 219                 /* form an index tuple and point it at the heap tuple */
 220                 itup = index_formtuple(itupdesc, attdata, nulls);
 221                 itup->t_tid = htup->t_self;
 222
 223                 /*
 224                  * Since we already have the index relation locked, we call
 225                  * gistdoinsert directly.  Normal access method calls dispatch
 226                  * through gistinsert, which locks the relation for write.      This
 227                  * is the right thing to do if you're inserting single tups, but
 228                  * not when you're initializing the whole index at once.
 229                  */
 230
 231                 res = gistdoinsert(index, itup, &giststate);
 232
 233                 for (i = 0; i < indexInfo->ii_NumIndexAttrs; i++)
 234                         if (compvec[i])
 235                                 pfree(DatumGetPointer(attdata[i]));
 236
 237                 pfree(itup);
 238                 pfree(res);
 239         }
 240
 241         /* okay, all heap tuples are indexed */
 242         heap_endscan(hscan);
 243
 244         pfree(compvec);
 245
 246 #ifndef OMIT_PARTIAL_INDEX
 247         if (pred != NULL || oldPred != NULL)
 248         {
 249                 ExecDropTupleTable(tupleTable, true);
 250         }
 251 #endif   /* OMIT_PARTIAL_INDEX */
 252         FreeExprContext(econtext);
 253
 254         /*
 255          * Since we just counted the tuples in the heap, we update its stats
 256          * in pg_class to guarantee that the planner takes advantage of the
 257          * index we just created.  But, only update statistics during normal
 258          * index definitions, not for indices on system catalogs created
 259          * during bootstrap processing.  We must close the relations before
 260          * updating statistics to guarantee that the relcache entries are
 261          * flushed when we increment the command counter in UpdateStats(). But
 262          * we do not release any locks on the relations; those will be held
 263          * until end of transaction.
 264          */
 265         if (IsNormalProcessingMode())
 266         {
 267                 Oid                     hrelid = RelationGetRelid(heap);
 268                 Oid                     irelid = RelationGetRelid(index);
 269                 bool            inplace = IsReindexProcessing();
 270
 271                 heap_close(heap, NoLock);
 272                 index_close(index);
 273                 UpdateStats(hrelid, nhtups, inplace);
 274                 UpdateStats(irelid, nitups, inplace);
 275                 if (oldPred != NULL && !inplace)
 276                 {
 277                         if (nitups == nhtups)
 278                                 pred = NULL;
 279                         UpdateIndexPredicate(irelid, oldPred, pred);
 280                 }
 281         }
 282
 283         PG_RETURN_VOID();
 284 }
 285
 286 /*
 287  *      gistinsert -- wrapper for GiST tuple insertion.
 288  *
 289  *        This is the public interface routine for tuple insertion in GiSTs.
 290  *        It doesn't do any work; just locks the relation and passes the buck.
 291  */
 292 Datum
 293 gistinsert(PG_FUNCTION_ARGS)
 294 {
 295         Relation                r = (Relation) PG_GETARG_POINTER(0);
 296         Datum              *datum = (Datum *) PG_GETARG_POINTER(1);
 297         char               *nulls = (char *) PG_GETARG_POINTER(2);
 298         ItemPointer             ht_ctid = (ItemPointer) PG_GETARG_POINTER(3);
 299 #ifdef NOT_USED
 300         Relation                heapRel = (Relation) PG_GETARG_POINTER(4);
 301 #endif
 302         InsertIndexResult res;
 303         IndexTuple      itup;
 304         GISTSTATE       giststate;
 305         GISTENTRY       tmpentry;
 306         int                     i;
 307         bool       *compvec;
 308
 309         initGISTstate(&giststate, r);
 310
 311         /* immediately compress keys to normalize */
 312         compvec = (bool *) palloc(sizeof(bool) * r->rd_att->natts);
 313         for (i = 0; i < r->rd_att->natts; i++)
 314         {
 315                 gistcentryinit(&giststate, &tmpentry, (char *) datum[i],
 316                                            (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
 317                                            -1 /* size is currently bogus */ , TRUE);
 318                 if (datum[i] != (Datum) tmpentry.pred && !(giststate.keytypbyval))
 319                         compvec[i] = TRUE;
 320                 else
 321                         compvec[i] = FALSE;
 322                 datum[i] = (Datum) tmpentry.pred;
 323         }
 324         itup = index_formtuple(RelationGetDescr(r), datum, nulls);
 325         itup->t_tid = *ht_ctid;
 326
 327         /*
 328          * Notes in ExecUtils:ExecOpenIndices()
 329          *
 330          * RelationSetLockForWrite(r);
 331          */
 332
 333         res = gistdoinsert(r, itup, &giststate);
 334         for (i = 0; i < r->rd_att->natts; i++)
 335                 if (compvec[i] == TRUE)
 336                         pfree((char *) datum[i]);
 337         pfree(itup);
 338         pfree(compvec);
 339
 340         PG_RETURN_POINTER(res);
 341 }
 342
 343 /*
 344 ** Take a compressed entry, and install it on a page.  Since we now know
 345 ** where the entry will live, we decompress it and recompress it using
 346 ** that knowledge (some compression routines may want to fish around
 347 ** on the page, for example, or do something special for leaf nodes.)
 348 */
 349 static OffsetNumber
 350 gistPageAddItem(GISTSTATE *giststate,
 351                                 Relation r,
 352                                 Page page,
 353                                 Item item,
 354                                 Size size,
 355                                 OffsetNumber offsetNumber,
 356                                 ItemIdFlags flags,
 357                                 GISTENTRY *dentry,
 358                                 IndexTuple *newtup)
 359 {
 360         GISTENTRY       tmpcentry;
 361         IndexTuple      itup = (IndexTuple) item;
 362
 363         /*
 364          * recompress the item given that we now know the exact page and
 365          * offset for insertion
 366          */
 367         gistdentryinit(giststate, dentry,
 368                                    (((char *) itup) + sizeof(IndexTupleData)),
 369                           (Relation) 0, (Page) 0, (OffsetNumber) InvalidOffsetNumber,
 370                                    IndexTupleSize(itup) - sizeof(IndexTupleData), FALSE);
 371         gistcentryinit(giststate, &tmpcentry, dentry->pred, r, page,
 372                                    offsetNumber, dentry->bytes, FALSE);
 373         *newtup = gist_tuple_replacekey(r, *dentry, itup);
 374         /* be tidy */
 375         if (tmpcentry.pred != dentry->pred
 376                 && tmpcentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
 377                 pfree(tmpcentry.pred);
 378
 379         return (PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
 380                                                 offsetNumber, flags));
 381 }
 382
 383
 384 static InsertIndexResult
 385 gistdoinsert(Relation r,
 386                          IndexTuple itup,       /* itup contains compressed entry */
 387                          GISTSTATE *giststate)
 388 {
 389         GISTENTRY       tmpdentry;
 390         InsertIndexResult res;
 391         OffsetNumber l;
 392         GISTSTACK  *stack;
 393         Buffer          buffer;
 394         BlockNumber blk;
 395         Page            page;
 396         OffsetNumber off;
 397         IndexTuple      newtup;
 398
 399         /* 3rd arg is ignored for now */
 400         blk = gistChooseSubtree(r, itup, 0, giststate, &stack, &buffer);
 401         page = (Page) BufferGetPage(buffer);
 402
 403         if (gistnospace(page, itup))
 404         {
 405                 /* need to do a split */
 406                 res = gistSplit(r, buffer, stack, itup, giststate);
 407                 gistfreestack(stack);
 408                 WriteBuffer(buffer);    /* don't forget to release buffer! */
 409                 return res;
 410         }
 411
 412         if (PageIsEmpty(page))
 413                 off = FirstOffsetNumber;
 414         else
 415                 off = OffsetNumberNext(PageGetMaxOffsetNumber(page));
 416
 417         /* add the item and write the buffer */
 418         l = gistPageAddItem(giststate, r, page, (Item) itup, IndexTupleSize(itup),
 419                                                 off, LP_USED, &tmpdentry, &newtup);
 420         WriteBuffer(buffer);
 421
 422         /* now expand the page boundary in the parent to include the new child */
 423         gistAdjustKeys(r, stack, blk, tmpdentry.pred, tmpdentry.bytes, giststate);
 424         gistfreestack(stack);
 425
 426         /* be tidy */
 427         if (itup != newtup)
 428                 pfree(newtup);
 429         if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
 430                 pfree(tmpdentry.pred);
 431
 432         /* build and return an InsertIndexResult for this insertion */
 433         res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
 434         ItemPointerSet(&(res->pointerData), blk, l);
 435
 436         return res;
 437 }
 438
 439
 440 static BlockNumber
 441 gistChooseSubtree(Relation r, IndexTuple itup,  /* itup has compressed
 442                                                                                                  * entry */
 443                                   int level,
 444                                   GISTSTATE *giststate,
 445                                   GISTSTACK **retstack /* out */ ,
 446                                   Buffer *leafbuf /* out */ )
 447 {
 448         Buffer          buffer;
 449         BlockNumber blk;
 450         GISTSTACK  *stack;
 451         Page            page;
 452         GISTPageOpaque opaque;
 453         IndexTuple      which;
 454
 455         blk = GISTP_ROOT;
 456         buffer = InvalidBuffer;
 457         stack = (GISTSTACK *) NULL;
 458
 459         do
 460         {
 461                 /* let go of current buffer before getting next */
 462                 if (buffer != InvalidBuffer)
 463                         ReleaseBuffer(buffer);
 464
 465                 /* get next buffer */
 466                 buffer = ReadBuffer(r, blk);
 467                 page = (Page) BufferGetPage(buffer);
 468
 469                 opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
 470                 if (!(opaque->flags & F_LEAF))
 471                 {
 472                         GISTSTACK  *n;
 473                         ItemId          iid;
 474
 475                         n = (GISTSTACK *) palloc(sizeof(GISTSTACK));
 476                         n->gs_parent = stack;
 477                         n->gs_blk = blk;
 478                         n->gs_child = gistchoose(r, page, itup, giststate);
 479                         stack = n;
 480
 481                         iid = PageGetItemId(page, n->gs_child);
 482                         which = (IndexTuple) PageGetItem(page, iid);
 483                         blk = ItemPointerGetBlockNumber(&(which->t_tid));
 484                 }
 485         } while (!(opaque->flags & F_LEAF));
 486
 487         *retstack = stack;
 488         *leafbuf = buffer;
 489
 490         return blk;
 491 }
 492
 493
 494 static void
 495 gistAdjustKeys(Relation r,
 496                            GISTSTACK *stk,
 497                            BlockNumber blk,
 498                            char *datum,         /* datum is uncompressed */
 499                            int att_size,
 500                            GISTSTATE *giststate)
 501 {
 502         char       *oldud;
 503         Page            p;
 504         Buffer          b;
 505         bool            result;
 506         bytea      *evec;
 507         GISTENTRY       centry,
 508                            *ev0p,
 509                            *ev1p;
 510         int                     size,
 511                                 datumsize;
 512         IndexTuple      tid;
 513
 514         if (stk == (GISTSTACK *) NULL)
 515                 return;
 516
 517         b = ReadBuffer(r, stk->gs_blk);
 518         p = BufferGetPage(b);
 519
 520         oldud = (char *) PageGetItem(p, PageGetItemId(p, stk->gs_child));
 521         tid = (IndexTuple) oldud;
 522         size = IndexTupleSize((IndexTuple) oldud) - sizeof(IndexTupleData);
 523         oldud += sizeof(IndexTupleData);
 524
 525         evec = (bytea *) palloc(2 * sizeof(GISTENTRY) + VARHDRSZ);
 526         VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
 527
 528         /* insert decompressed oldud into entry vector */
 529         gistdentryinit(giststate, &((GISTENTRY *) VARDATA(evec))[0],
 530                                    oldud, r, p, stk->gs_child,
 531                                    size, FALSE);
 532         ev0p = &((GISTENTRY *) VARDATA(evec))[0];
 533
 534         /* insert datum entry into entry vector */
 535         gistentryinit(((GISTENTRY *) VARDATA(evec))[1], datum,
 536                 (Relation) NULL, (Page) NULL, (OffsetNumber) 0, att_size, FALSE);
 537         ev1p = &((GISTENTRY *) VARDATA(evec))[1];
 538
 539         /* form union of decompressed entries */
 540         datum = (char *)
 541                 DatumGetPointer(FunctionCall2(&giststate->unionFn,
 542                                                                           PointerGetDatum(evec),
 543                                                                           PointerGetDatum(&datumsize)));
 544
 545         /* did union leave decompressed version of oldud unchanged? */
 546         FunctionCall3(&giststate->equalFn,
 547                                   PointerGetDatum(ev0p->pred),
 548                                   PointerGetDatum(datum),
 549                                   PointerGetDatum(&result));
 550         if (!result)
 551         {
 552                 TupleDesc       td = RelationGetDescr(r);
 553
 554                 /* compress datum for storage on page */
 555                 gistcentryinit(giststate, &centry, datum, ev0p->rel, ev0p->page,
 556                                            ev0p->offset, datumsize, FALSE);
 557                 if (td->attrs[0]->attlen >= 0)
 558                 {
 559                         memmove(oldud, centry.pred, att_size);
 560                         gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
 561                                                    giststate);
 562                 }
 563                 else if (VARSIZE(centry.pred) == VARSIZE(oldud))
 564                 {
 565                         memmove(oldud, centry.pred, VARSIZE(centry.pred));
 566                         gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, datum, att_size,
 567                                                    giststate);
 568                 }
 569                 else
 570                 {
 571
 572                         /*
 573                          * * new datum is not the same size as the old. * We have to
 574                          * delete the old entry and insert the new * one.  Note that
 575                          * this may cause a split here!
 576                          */
 577                         IndexTuple      newtup;
 578                         ItemPointerData oldtid;
 579                         char       *isnull;
 580                         TupleDesc       tupDesc;
 581                         InsertIndexResult res;
 582
 583                         /* delete old tuple */
 584                         ItemPointerSet(&oldtid, stk->gs_blk, stk->gs_child);
 585                         DirectFunctionCall2(gistdelete,
 586                                                                 PointerGetDatum(r),
 587                                                                 PointerGetDatum(&oldtid));
 588
 589                         /* generate and insert new tuple */
 590                         tupDesc = r->rd_att;
 591                         isnull = (char *) palloc(r->rd_rel->relnatts);
 592                         MemSet(isnull, ' ', r->rd_rel->relnatts);
 593                         newtup = (IndexTuple) index_formtuple(tupDesc,
 594                                                                                  (Datum *) &centry.pred, isnull);
 595                         pfree(isnull);
 596                         /* set pointer in new tuple to point to current child */
 597                         ItemPointerSet(&oldtid, blk, 1);
 598                         newtup->t_tid = oldtid;
 599
 600                         /* inserting the new entry also adjust keys above */
 601                         res = gistentryinsert(r, stk, newtup, giststate);
 602
 603                         /* in stack, set info to point to new tuple */
 604                         stk->gs_blk = ItemPointerGetBlockNumber(&(res->pointerData));
 605                         stk->gs_child = ItemPointerGetOffsetNumber(&(res->pointerData));
 606
 607                         pfree(res);
 608                 }
 609                 WriteBuffer(b);
 610
 611                 if (centry.pred != datum)
 612                         pfree(datum);
 613         }
 614         else
 615                 ReleaseBuffer(b);
 616         pfree(evec);
 617 }
 618
 619 /*
 620  *      gistSplit -- split a page in the tree.
 621  *
 622  */
 623 static InsertIndexResult
 624 gistSplit(Relation r,
 625                   Buffer buffer,
 626                   GISTSTACK *stack,
 627                   IndexTuple itup,              /* contains compressed entry */
 628                   GISTSTATE *giststate)
 629 {
 630         Page            p;
 631         Buffer          leftbuf,
 632                                 rightbuf;
 633         Page            left,
 634                                 right;
 635         ItemId          itemid;
 636         IndexTuple      item;
 637         IndexTuple      ltup,
 638                                 rtup,
 639                                 newtup;
 640         OffsetNumber maxoff;
 641         OffsetNumber i;
 642         OffsetNumber leftoff,
 643                                 rightoff;
 644         BlockNumber lbknum,
 645                                 rbknum;
 646         BlockNumber bufblock;
 647         GISTPageOpaque opaque;
 648         int                     blank;
 649         InsertIndexResult res;
 650         char       *isnull;
 651         GIST_SPLITVEC v;
 652         TupleDesc       tupDesc;
 653         bytea      *entryvec;
 654         bool       *decompvec;
 655         IndexTuple      item_1;
 656         GISTENTRY       tmpdentry,
 657                                 tmpentry;
 658
 659         isnull = (char *) palloc(r->rd_rel->relnatts);
 660         for (blank = 0; blank < r->rd_rel->relnatts; blank++)
 661                 isnull[blank] = ' ';
 662         p = (Page) BufferGetPage(buffer);
 663         opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
 664
 665
 666         /*
 667          * The root of the tree is the first block in the relation.  If we're
 668          * about to split the root, we need to do some hocus-pocus to enforce
 669          * this guarantee.
 670          */
 671
 672         if (BufferGetBlockNumber(buffer) == GISTP_ROOT)
 673         {
 674                 leftbuf = ReadBuffer(r, P_NEW);
 675                 GISTInitBuffer(leftbuf, opaque->flags);
 676                 lbknum = BufferGetBlockNumber(leftbuf);
 677                 left = (Page) BufferGetPage(leftbuf);
 678         }
 679         else
 680         {
 681                 leftbuf = buffer;
 682                 IncrBufferRefCount(buffer);
 683                 lbknum = BufferGetBlockNumber(buffer);
 684                 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
 685         }
 686
 687         rightbuf = ReadBuffer(r, P_NEW);
 688         GISTInitBuffer(rightbuf, opaque->flags);
 689         rbknum = BufferGetBlockNumber(rightbuf);
 690         right = (Page) BufferGetPage(rightbuf);
 691
 692         /* generate the item array */
 693         maxoff = PageGetMaxOffsetNumber(p);
 694         entryvec = (bytea *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(GISTENTRY));
 695         decompvec = (bool *) palloc(VARHDRSZ + (maxoff + 2) * sizeof(bool));
 696         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 697         {
 698                 item_1 = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
 699                 gistdentryinit(giststate, &((GISTENTRY *) VARDATA(entryvec))[i],
 700                                            (((char *) item_1) + sizeof(IndexTupleData)),
 701                                            r, p, i,
 702                                  IndexTupleSize(item_1) - sizeof(IndexTupleData), FALSE);
 703                 if ((char *) (((GISTENTRY *) VARDATA(entryvec))[i].pred)
 704                         == (((char *) item_1) + sizeof(IndexTupleData)))
 705                         decompvec[i] = FALSE;
 706                 else
 707                         decompvec[i] = TRUE;
 708         }
 709
 710         /* add the new datum as the last entry */
 711         gistdentryinit(giststate, &(((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]),
 712                                    (((char *) itup) + sizeof(IndexTupleData)),
 713                                    (Relation) NULL, (Page) NULL,
 714                                    (OffsetNumber) 0, tmpentry.bytes, FALSE);
 715         if ((char *) (((GISTENTRY *) VARDATA(entryvec))[maxoff + 1]).pred !=
 716                 (((char *) itup) + sizeof(IndexTupleData)))
 717                 decompvec[maxoff + 1] = TRUE;
 718         else
 719                 decompvec[maxoff + 1] = FALSE;
 720
 721         VARATT_SIZEP(entryvec) = (maxoff + 2) * sizeof(GISTENTRY) + VARHDRSZ;
 722
 723         /* now let the user-defined picksplit function set up the split vector */
 724         FunctionCall2(&giststate->picksplitFn,
 725                                   PointerGetDatum(entryvec),
 726                                   PointerGetDatum(&v));
 727
 728         /* compress ldatum and rdatum */
 729         gistcentryinit(giststate, &tmpentry, v.spl_ldatum, (Relation) NULL,
 730                                    (Page) NULL, (OffsetNumber) 0,
 731                                    ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
 732         if (v.spl_ldatum != tmpentry.pred)
 733                 pfree(v.spl_ldatum);
 734         v.spl_ldatum = tmpentry.pred;
 735
 736         gistcentryinit(giststate, &tmpentry, v.spl_rdatum, (Relation) NULL,
 737                                    (Page) NULL, (OffsetNumber) 0,
 738                                    ((GISTENTRY *) VARDATA(entryvec))[i].bytes, FALSE);
 739         if (v.spl_rdatum != tmpentry.pred)
 740                 pfree(v.spl_rdatum);
 741         v.spl_rdatum = tmpentry.pred;
 742
 743         /* clean up the entry vector: its preds need to be deleted, too */
 744         for (i = FirstOffsetNumber; i <= maxoff + 1; i = OffsetNumberNext(i))
 745                 if (decompvec[i])
 746                         pfree(((GISTENTRY *) VARDATA(entryvec))[i].pred);
 747         pfree(entryvec);
 748         pfree(decompvec);
 749
 750         leftoff = rightoff = FirstOffsetNumber;
 751         maxoff = PageGetMaxOffsetNumber(p);
 752         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 753         {
 754                 itemid = PageGetItemId(p, i);
 755                 item = (IndexTuple) PageGetItem(p, itemid);
 756
 757                 if (i == *(v.spl_left))
 758                 {
 759                         gistPageAddItem(giststate, r, left, (Item) item,
 760                                                         IndexTupleSize(item),
 761                                                         leftoff, LP_USED, &tmpdentry, &newtup);
 762                         leftoff = OffsetNumberNext(leftoff);
 763                         v.spl_left++;           /* advance in left split vector */
 764                         /* be tidy */
 765                         if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
 766                                 pfree(tmpdentry.pred);
 767                         if ((IndexTuple) item != newtup)
 768                                 pfree(newtup);
 769                 }
 770                 else
 771                 {
 772                         gistPageAddItem(giststate, r, right, (Item) item,
 773                                                         IndexTupleSize(item),
 774                                                         rightoff, LP_USED, &tmpdentry, &newtup);
 775                         rightoff = OffsetNumberNext(rightoff);
 776                         v.spl_right++;          /* advance in right split vector */
 777                         /* be tidy */
 778                         if (tmpdentry.pred != (((char *) item) + sizeof(IndexTupleData)))
 779                                 pfree(tmpdentry.pred);
 780                         if (item != newtup)
 781                                 pfree(newtup);
 782                 }
 783         }
 784
 785         /* build an InsertIndexResult for this insertion */
 786         res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
 787
 788         /* now insert the new index tuple */
 789         if (*(v.spl_left) != FirstOffsetNumber)
 790         {
 791                 gistPageAddItem(giststate, r, left, (Item) itup,
 792                                                 IndexTupleSize(itup),
 793                                                 leftoff, LP_USED, &tmpdentry, &newtup);
 794                 leftoff = OffsetNumberNext(leftoff);
 795                 ItemPointerSet(&(res->pointerData), lbknum, leftoff);
 796                 /* be tidy */
 797                 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
 798                         pfree(tmpdentry.pred);
 799                 if (itup != newtup)
 800                         pfree(newtup);
 801         }
 802         else
 803         {
 804                 gistPageAddItem(giststate, r, right, (Item) itup,
 805                                                 IndexTupleSize(itup),
 806                                                 rightoff, LP_USED, &tmpdentry, &newtup);
 807                 rightoff = OffsetNumberNext(rightoff);
 808                 ItemPointerSet(&(res->pointerData), rbknum, rightoff);
 809                 /* be tidy */
 810                 if (tmpdentry.pred != (((char *) itup) + sizeof(IndexTupleData)))
 811                         pfree(tmpdentry.pred);
 812                 if (itup != newtup)
 813                         pfree(newtup);
 814         }
 815
 816         if ((bufblock = BufferGetBlockNumber(buffer)) != GISTP_ROOT)
 817                 PageRestoreTempPage(left, p);
 818         WriteBuffer(leftbuf);
 819         WriteBuffer(rightbuf);
 820
 821         /*
 822          * Okay, the page is split.  We have three things left to do:
 823          *
 824          * 1)  Adjust any active scans on this index to cope with changes we
 825          * introduced in its structure by splitting this page.
 826          *
 827          * 2)  "Tighten" the bounding box of the pointer to the left page in the
 828          * parent node in the tree, if any.  Since we moved a bunch of stuff
 829          * off the left page, we expect it to get smaller.      This happens in
 830          * the internal insertion routine.
 831          *
 832          * 3)  Insert a pointer to the right page in the parent.  This may cause
 833          * the parent to split.  If it does, we need to repeat steps one and
 834          * two for each split node in the tree.
 835          */
 836
 837         /* adjust active scans */
 838         gistadjscans(r, GISTOP_SPLIT, bufblock, FirstOffsetNumber);
 839
 840         tupDesc = r->rd_att;
 841
 842         ltup = (IndexTuple) index_formtuple(tupDesc,
 843                                                                           (Datum *) &(v.spl_ldatum), isnull);
 844         rtup = (IndexTuple) index_formtuple(tupDesc,
 845                                                                           (Datum *) &(v.spl_rdatum), isnull);
 846         pfree(isnull);
 847
 848         /* set pointers to new child pages in the internal index tuples */
 849         ItemPointerSet(&(ltup->t_tid), lbknum, 1);
 850         ItemPointerSet(&(rtup->t_tid), rbknum, 1);
 851
 852         gistintinsert(r, stack, ltup, rtup, giststate);
 853
 854         pfree(ltup);
 855         pfree(rtup);
 856
 857         return res;
 858 }
 859
 860 /*
 861 ** After a split, we need to overwrite the old entry's key in the parent,
 862 ** and install install an entry for the new key into the parent.
 863 */
 864 static void
 865 gistintinsert(Relation r,
 866                           GISTSTACK *stk,
 867                           IndexTuple ltup,      /* new version of entry for old page */
 868                           IndexTuple rtup,      /* entry for new page */
 869                           GISTSTATE *giststate)
 870 {
 871         ItemPointerData ltid;
 872
 873         if (stk == (GISTSTACK *) NULL)
 874         {
 875                 gistnewroot(giststate, r, ltup, rtup);
 876                 return;
 877         }
 878
 879         /* remove old left pointer, insert the 2 new entries */
 880         ItemPointerSet(&ltid, stk->gs_blk, stk->gs_child);
 881         DirectFunctionCall2(gistdelete,
 882                                                 PointerGetDatum(r),
 883                                                 PointerGetDatum(&ltid));
 884         gistentryinserttwo(r, stk, ltup, rtup, giststate);
 885 }
 886
 887
 888 /*
 889 ** Insert two entries onto one page, handling a split for either one!
 890 */
 891 static void
 892 gistentryinserttwo(Relation r, GISTSTACK *stk, IndexTuple ltup,
 893                                    IndexTuple rtup, GISTSTATE *giststate)
 894 {
 895         Buffer          b;
 896         Page            p;
 897         InsertIndexResult res;
 898         GISTENTRY       tmpentry;
 899         IndexTuple      newtup;
 900
 901         b = ReadBuffer(r, stk->gs_blk);
 902         p = BufferGetPage(b);
 903
 904         if (gistnospace(p, ltup))
 905         {
 906                 res = gistSplit(r, b, stk->gs_parent, ltup, giststate);
 907                 WriteBuffer(b);                 /* don't forget to release buffer!  -
 908                                                                  * 01/31/94 */
 909                 pfree(res);
 910                 gistdoinsert(r, rtup, giststate);
 911         }
 912         else
 913         {
 914                 gistPageAddItem(giststate, r, p, (Item) ltup,
 915                                                 IndexTupleSize(ltup), InvalidOffsetNumber,
 916                                                 LP_USED, &tmpentry, &newtup);
 917                 WriteBuffer(b);
 918                 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
 919                                            tmpentry.bytes, giststate);
 920                 /* be tidy */
 921                 if (tmpentry.pred != (((char *) ltup) + sizeof(IndexTupleData)))
 922                         pfree(tmpentry.pred);
 923                 if (ltup != newtup)
 924                         pfree(newtup);
 925                 gistentryinsert(r, stk, rtup, giststate);
 926         }
 927 }
 928
 929
 930 /*
 931 ** Insert an entry onto a page
 932 */
 933 static InsertIndexResult
 934 gistentryinsert(Relation r, GISTSTACK *stk, IndexTuple tup,
 935                                 GISTSTATE *giststate)
 936 {
 937         Buffer          b;
 938         Page            p;
 939         InsertIndexResult res;
 940         OffsetNumber off;
 941         GISTENTRY       tmpentry;
 942         IndexTuple      newtup;
 943
 944         b = ReadBuffer(r, stk->gs_blk);
 945         p = BufferGetPage(b);
 946
 947         if (gistnospace(p, tup))
 948         {
 949                 res = gistSplit(r, b, stk->gs_parent, tup, giststate);
 950                 WriteBuffer(b);                 /* don't forget to release buffer!  -
 951                                                                  * 01/31/94 */
 952                 return res;
 953         }
 954         else
 955         {
 956                 res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
 957                 off = gistPageAddItem(giststate, r, p, (Item) tup, IndexTupleSize(tup),
 958                                            InvalidOffsetNumber, LP_USED, &tmpentry, &newtup);
 959                 WriteBuffer(b);
 960                 ItemPointerSet(&(res->pointerData), stk->gs_blk, off);
 961                 gistAdjustKeys(r, stk->gs_parent, stk->gs_blk, tmpentry.pred,
 962                                            tmpentry.bytes, giststate);
 963                 /* be tidy */
 964                 if (tmpentry.pred != (((char *) tup) + sizeof(IndexTupleData)))
 965                         pfree(tmpentry.pred);
 966                 if (tup != newtup)
 967                         pfree(newtup);
 968                 return res;
 969         }
 970 }
 971
 972
 973 static void
 974 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple lt, IndexTuple rt)
 975 {
 976         Buffer          b;
 977         Page            p;
 978         GISTENTRY       tmpentry;
 979         IndexTuple      newtup;
 980
 981         b = ReadBuffer(r, GISTP_ROOT);
 982         GISTInitBuffer(b, 0);
 983         p = BufferGetPage(b);
 984         gistPageAddItem(giststate, r, p, (Item) lt, IndexTupleSize(lt),
 985                                         FirstOffsetNumber,
 986                                         LP_USED, &tmpentry, &newtup);
 987         /* be tidy */
 988         if (tmpentry.pred != (((char *) lt) + sizeof(IndexTupleData)))
 989                 pfree(tmpentry.pred);
 990         if (lt != newtup)
 991                 pfree(newtup);
 992         gistPageAddItem(giststate, r, p, (Item) rt, IndexTupleSize(rt),
 993                                         OffsetNumberNext(FirstOffsetNumber), LP_USED,
 994                                         &tmpentry, &newtup);
 995         /* be tidy */
 996         if (tmpentry.pred != (((char *) rt) + sizeof(IndexTupleData)))
 997                 pfree(tmpentry.pred);
 998         if (rt != newtup)
 999                 pfree(newtup);
1000         WriteBuffer(b);
1001 }
1002
1003 static void
1004 GISTInitBuffer(Buffer b, uint32 f)
1005 {
1006         GISTPageOpaque opaque;
1007         Page            page;
1008         Size            pageSize;
1009
1010         pageSize = BufferGetPageSize(b);
1011
1012         page = BufferGetPage(b);
1013         MemSet(page, 0, (int) pageSize);
1014         PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
1015
1016         opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1017         opaque->flags = f;
1018 }
1019
1020
1021 /*
1022 ** find entry with lowest penalty
1023 */
1024 static OffsetNumber
1025 gistchoose(Relation r, Page p, IndexTuple it,   /* it has compressed entry */
1026                    GISTSTATE *giststate)
1027 {
1028         OffsetNumber maxoff;
1029         OffsetNumber i;
1030         char       *id;
1031         char       *datum;
1032         float           usize;
1033         OffsetNumber which;
1034         float           which_grow;
1035         GISTENTRY       entry,
1036                                 identry;
1037         int                     size,
1038                                 idsize;
1039
1040         idsize = IndexTupleSize(it) - sizeof(IndexTupleData);
1041         id = ((char *) it) + sizeof(IndexTupleData);
1042         maxoff = PageGetMaxOffsetNumber(p);
1043         which_grow = -1.0;
1044         which = -1;
1045
1046         gistdentryinit(giststate, &identry, id, (Relation) NULL, (Page) NULL,
1047                                    (OffsetNumber) 0, idsize, FALSE);
1048
1049         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1050         {
1051                 datum = (char *) PageGetItem(p, PageGetItemId(p, i));
1052                 size = IndexTupleSize(datum) - sizeof(IndexTupleData);
1053                 datum += sizeof(IndexTupleData);
1054                 gistdentryinit(giststate, &entry, datum, r, p, i, size, FALSE);
1055                 FunctionCall3(&giststate->penaltyFn,
1056                                           PointerGetDatum(&entry),
1057                                           PointerGetDatum(&identry),
1058                                           PointerGetDatum(&usize));
1059                 if (which_grow < 0 || usize < which_grow)
1060                 {
1061                         which = i;
1062                         which_grow = usize;
1063                         if (which_grow == 0)
1064                                 break;
1065                 }
1066                 if (entry.pred != datum)
1067                         pfree(entry.pred);
1068         }
1069         if (identry.pred != id)
1070                 pfree(identry.pred);
1071
1072         return which;
1073 }
1074
1075 static int
1076 gistnospace(Page p, IndexTuple it)
1077 {
1078         return PageGetFreeSpace(p) < IndexTupleSize(it);
1079 }
1080
1081 void
1082 gistfreestack(GISTSTACK *s)
1083 {
1084         GISTSTACK  *p;
1085
1086         while (s != (GISTSTACK *) NULL)
1087         {
1088                 p = s->gs_parent;
1089                 pfree(s);
1090                 s = p;
1091         }
1092 }
1093
1094
1095 /*
1096 ** remove an entry from a page
1097 */
1098 Datum
1099 gistdelete(PG_FUNCTION_ARGS)
1100 {
1101         Relation                r = (Relation) PG_GETARG_POINTER(0);
1102         ItemPointer             tid = (ItemPointer) PG_GETARG_POINTER(1);
1103         BlockNumber blkno;
1104         OffsetNumber offnum;
1105         Buffer          buf;
1106         Page            page;
1107
1108         /*
1109          * Notes in ExecUtils:ExecOpenIndices() Also note that only vacuum
1110          * deletes index tuples now...
1111          *
1112          * RelationSetLockForWrite(r);
1113          */
1114
1115         blkno = ItemPointerGetBlockNumber(tid);
1116         offnum = ItemPointerGetOffsetNumber(tid);
1117
1118         /* adjust any scans that will be affected by this deletion */
1119         gistadjscans(r, GISTOP_DEL, blkno, offnum);
1120
1121         /* delete the index tuple */
1122         buf = ReadBuffer(r, blkno);
1123         page = BufferGetPage(buf);
1124
1125         PageIndexTupleDelete(page, offnum);
1126
1127         WriteBuffer(buf);
1128
1129         PG_RETURN_VOID();
1130 }
1131
1132 void
1133 initGISTstate(GISTSTATE *giststate, Relation index)
1134 {
1135         RegProcedure consistent_proc,
1136                                 union_proc,
1137                                 compress_proc,
1138                                 decompress_proc;
1139         RegProcedure penalty_proc,
1140                                 picksplit_proc,
1141                                 equal_proc;
1142         HeapTuple       htup;
1143         Form_pg_index itupform;
1144
1145         consistent_proc = index_getprocid(index, 1, GIST_CONSISTENT_PROC);
1146         union_proc = index_getprocid(index, 1, GIST_UNION_PROC);
1147         compress_proc = index_getprocid(index, 1, GIST_COMPRESS_PROC);
1148         decompress_proc = index_getprocid(index, 1, GIST_DECOMPRESS_PROC);
1149         penalty_proc = index_getprocid(index, 1, GIST_PENALTY_PROC);
1150         picksplit_proc = index_getprocid(index, 1, GIST_PICKSPLIT_PROC);
1151         equal_proc = index_getprocid(index, 1, GIST_EQUAL_PROC);
1152         fmgr_info(consistent_proc, &giststate->consistentFn);
1153         fmgr_info(union_proc, &giststate->unionFn);
1154         fmgr_info(compress_proc, &giststate->compressFn);
1155         fmgr_info(decompress_proc, &giststate->decompressFn);
1156         fmgr_info(penalty_proc, &giststate->penaltyFn);
1157         fmgr_info(picksplit_proc, &giststate->picksplitFn);
1158         fmgr_info(equal_proc, &giststate->equalFn);
1159
1160         /* see if key type is different from type of attribute being indexed */
1161         htup = SearchSysCacheTuple(INDEXRELID,
1162                                                            ObjectIdGetDatum(RelationGetRelid(index)),
1163                                                            0, 0, 0);
1164         itupform = (Form_pg_index) GETSTRUCT(htup);
1165         if (!HeapTupleIsValid(htup))
1166                 elog(ERROR, "initGISTstate: index %u not found",
1167                          RelationGetRelid(index));
1168         giststate->haskeytype = itupform->indhaskeytype;
1169         if (giststate->haskeytype)
1170         {
1171                 /* key type is different -- is it byval? */
1172                 htup = SearchSysCacheTuple(ATTNUM,
1173                                                                    ObjectIdGetDatum(itupform->indexrelid),
1174                                                                    UInt16GetDatum(FirstOffsetNumber),
1175                                                                    0, 0);
1176                 if (!HeapTupleIsValid(htup))
1177                 {
1178                         elog(ERROR, "initGISTstate: no attribute tuple %u %d",
1179                                  itupform->indexrelid, FirstOffsetNumber);
1180                         return;
1181                 }
1182                 giststate->keytypbyval = (((Form_pg_attribute) htup)->attbyval);
1183         }
1184         else
1185                 giststate->keytypbyval = FALSE;
1186         return;
1187 }
1188
1189
1190 /*
1191 ** Given an IndexTuple to be inserted on a page, this routine replaces
1192 ** the key with another key, which may involve generating a new IndexTuple
1193 ** if the sizes don't match
1194 */
1195 static IndexTuple
1196 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1197 {
1198         char       *datum = (((char *) t) + sizeof(IndexTupleData));
1199
1200         /* if new entry fits in index tuple, copy it in */
1201         if ((Size) entry.bytes < IndexTupleSize(t) - sizeof(IndexTupleData))
1202         {
1203                 memcpy(datum, entry.pred, entry.bytes);
1204                 /* clear out old size */
1205                 t->t_info &= 0xe000;
1206                 /* or in new size */
1207                 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1208
1209                 return t;
1210         }
1211         else
1212         {
1213                 /* generate a new index tuple for the compressed entry */
1214                 TupleDesc       tupDesc = r->rd_att;
1215                 IndexTuple      newtup;
1216                 char       *isnull;
1217                 int                     blank;
1218
1219                 isnull = (char *) palloc(r->rd_rel->relnatts);
1220                 for (blank = 0; blank < r->rd_rel->relnatts; blank++)
1221                         isnull[blank] = ' ';
1222                 newtup = (IndexTuple) index_formtuple(tupDesc,
1223                                                                                           (Datum *) &(entry.pred),
1224                                                                                           isnull);
1225                 newtup->t_tid = t->t_tid;
1226                 pfree(isnull);
1227                 return newtup;
1228         }
1229 }
1230
1231
1232 /*
1233 ** initialize a GiST entry with a decompressed version of pred
1234 */
1235 void
1236 gistdentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1237                            Page pg, OffsetNumber o, int b, bool l)
1238 {
1239         GISTENTRY  *dep;
1240
1241         gistentryinit(*e, pr, r, pg, o, b, l);
1242         if (giststate->haskeytype)
1243         {
1244                 dep = (GISTENTRY *)
1245                         DatumGetPointer(FunctionCall1(&giststate->decompressFn,
1246                                                                                   PointerGetDatum(e)));
1247                 gistentryinit(*e, dep->pred, dep->rel, dep->page, dep->offset, dep->bytes,
1248                                           dep->leafkey);
1249                 if (dep != e)
1250                         pfree(dep);
1251         }
1252 }
1253
1254
1255 /*
1256 ** initialize a GiST entry with a compressed version of pred
1257 */
1258 static void
1259 gistcentryinit(GISTSTATE *giststate, GISTENTRY *e, char *pr, Relation r,
1260                            Page pg, OffsetNumber o, int b, bool l)
1261 {
1262         GISTENTRY  *cep;
1263
1264         gistentryinit(*e, pr, r, pg, o, b, l);
1265         if (giststate->haskeytype)
1266         {
1267                 cep = (GISTENTRY *)
1268                         DatumGetPointer(FunctionCall1(&giststate->compressFn,
1269                                                                                   PointerGetDatum(e)));
1270                 gistentryinit(*e, cep->pred, cep->rel, cep->page, cep->offset, cep->bytes,
1271                                           cep->leafkey);
1272                 if (cep != e)
1273                         pfree(cep);
1274         }
1275 }
1276
1277
1278
1279 #ifdef GISTDEBUG
1280
1281 /*
1282 ** sloppy debugging support routine, requires recompilation with appropriate
1283 ** "out" method for the index keys.  Could be fixed to find that info
1284 ** in the catalogs...
1285 */
1286 void
1287 _gistdump(Relation r)
1288 {
1289         Buffer          buf;
1290         Page            page;
1291         OffsetNumber offnum,
1292                                 maxoff;
1293         BlockNumber blkno;
1294         BlockNumber nblocks;
1295         GISTPageOpaque po;
1296         IndexTuple      itup;
1297         BlockNumber itblkno;
1298         OffsetNumber itoffno;
1299         char       *datum;
1300         char       *itkey;
1301
1302         nblocks = RelationGetNumberOfBlocks(r);
1303         for (blkno = 0; blkno < nblocks; blkno++)
1304         {
1305                 buf = ReadBuffer(r, blkno);
1306                 page = BufferGetPage(buf);
1307                 po = (GISTPageOpaque) PageGetSpecialPointer(page);
1308                 maxoff = PageGetMaxOffsetNumber(page);
1309                 printf("Page %d maxoff %d <%s>\n", blkno, maxoff,
1310                            (po->flags & F_LEAF ? "LEAF" : "INTERNAL"));
1311
1312                 if (PageIsEmpty(page))
1313                 {
1314                         ReleaseBuffer(buf);
1315                         continue;
1316                 }
1317
1318                 for (offnum = FirstOffsetNumber;
1319                          offnum <= maxoff;
1320                          offnum = OffsetNumberNext(offnum))
1321                 {
1322                         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum));
1323                         itblkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1324                         itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid));
1325                         datum = ((char *) itup);
1326                         datum += sizeof(IndexTupleData);
1327                         /* get out function for type of key, and out it! */
1328                         itkey = (char *) int_range_out((INTRANGE *) datum);
1329                         /* itkey = " unable to print"; */
1330                         printf("\t[%d] size %d heap <%d,%d> key:%s\n",
1331                                    offnum, IndexTupleSize(itup), itblkno, itoffno, itkey);
1332                         pfree(itkey);
1333                 }
1334
1335                 ReleaseBuffer(buf);
1336         }
1337 }
1338
1339 static char *
1340 int_range_out(INTRANGE *r)
1341 {
1342         char       *result;
1343
1344         if (r == NULL)
1345                 return NULL;
1346         result = (char *) palloc(80);
1347         snprintf(result, 80, "[%d,%d): %d", r->lower, r->upper, r->flag);
1348
1349         return result;
1350 }
1351
1352 #endif   /* defined GISTDEBUG */
1353
1354 #ifdef XLOG
1355 void
1356 gist_redo(XLogRecPtr lsn, XLogRecord *record)
1357 {
1358         elog(STOP, "gist_redo: unimplemented");
1359 }
1360
1361 void
1362 gist_undo(XLogRecPtr lsn, XLogRecord *record)
1363 {
1364         elog(STOP, "gist_undo: unimplemented");
1365 }
1366
1367 void
1368 gist_desc(char *buf, uint8 xl_info, char* rec)
1369 {
1370 }
1371 #endif