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