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