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