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