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