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