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