granicus.if.org Git - postgresql/blob - src/backend/access/gist/gist.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gist.c
   4  *        interface routines for the postgres GiST index access method.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/access/gist/gist.c,v 1.88 2002/02/11 22:41:59 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  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 "miscadmin.h"
  23
  24
  25 #undef GIST_PAGEADDITEM
  26
  27 #define ATTSIZE( datum, TupDesc, i, isnull ) \
  28         ( \
  29                 ( isnull ) ? 0 : \
  30                         att_addlength(0, (TupDesc)->attrs[(i)-1]->attlen, (datum)) \
  31         )
  32
  33 /* result's status */
  34 #define INSERTED        0x01
  35 #define SPLITED         0x02
  36
  37 /* group flags ( in gistSplit ) */
  38 #define LEFT_ADDED      0x01
  39 #define RIGHT_ADDED 0x02
  40 #define BOTH_ADDED      ( LEFT_ADDED | RIGHT_ADDED )
  41
  42 /*
  43  * This defines only for shorter code, used in gistgetadjusted
  44  * and gistadjsubkey only
  45  */
  46 #define FILLITEM(evp, isnullkey, okey, okeyb, rkey, rkeyb)       do { \
  47                 if ( isnullkey ) {                                                                                \
  48                                 gistentryinit((evp), rkey, r, (Page) NULL ,               \
  49                                                 (OffsetNumber) 0, rkeyb, FALSE);                  \
  50                 } else {                                                                                                  \
  51                                 gistentryinit((evp), okey, r, (Page) NULL,                \
  52                                                 (OffsetNumber) 0, okeyb, FALSE);                  \
  53                 }                                                                                                                 \
  54 } while(0)
  55
  56 #define FILLEV(isnull1, key1, key1b, isnull2, key2, key2b) do { \
  57         FILLITEM(*ev0p, isnull1, key1, key1b, key2, key2b);             \
  58         FILLITEM(*ev1p, isnull2, key2, key2b, key1, key1b);             \
  59 } while(0);
  60
  61 /* Working state for gistbuild and its callback */
  62 typedef struct
  63 {
  64         GISTSTATE       giststate;
  65         int                     numindexattrs;
  66         double          indtuples;
  67 } GISTBuildState;
  68
  69
  70 /* non-export function prototypes */
  71 static void gistbuildCallback(Relation index,
  72                                   HeapTuple htup,
  73                                   Datum *attdata,
  74                                   char *nulls,
  75                                   bool tupleIsAlive,
  76                                   void *state);
  77 static void gistdoinsert(Relation r,
  78                          IndexTuple itup,
  79                          InsertIndexResult *res,
  80                          GISTSTATE *GISTstate);
  81 static int gistlayerinsert(Relation r, BlockNumber blkno,
  82                                 IndexTuple **itup,
  83                                 int *len,
  84                                 InsertIndexResult *res,
  85                                 GISTSTATE *giststate);
  86 static OffsetNumber gistwritebuffer(Relation r,
  87                                 Page page,
  88                                 IndexTuple *itup,
  89                                 int len,
  90                                 OffsetNumber off,
  91                                 GISTSTATE *giststate);
  92 static int gistnospace(Page page,
  93                         IndexTuple *itvec, int len);
  94 static IndexTuple *gistreadbuffer(Relation r,
  95                            Buffer buffer, int *len);
  96 static IndexTuple *gistjoinvector(
  97                            IndexTuple *itvec, int *len,
  98                            IndexTuple *additvec, int addlen);
  99 static IndexTuple gistunion(Relation r, IndexTuple *itvec,
 100                   int len, GISTSTATE *giststate);
 101
 102 static IndexTuple gistgetadjusted(Relation r,
 103                                 IndexTuple oldtup,
 104                                 IndexTuple addtup,
 105                                 GISTSTATE *giststate);
 106 static int gistfindgroup(GISTSTATE *giststate,
 107                           GISTENTRY *valvec, GIST_SPLITVEC *spl);
 108 static void gistadjsubkey(Relation r,
 109                           IndexTuple *itup, int *len,
 110                           GIST_SPLITVEC *v,
 111                           GISTSTATE *giststate);
 112 static IndexTuple gistFormTuple(GISTSTATE *giststate,
 113                         Relation r, Datum attdata[], int datumsize[], bool isnull[]);
 114 static IndexTuple *gistSplit(Relation r,
 115                   Buffer buffer,
 116                   IndexTuple *itup,
 117                   int *len,
 118                   GISTSTATE *giststate,
 119                   InsertIndexResult *res);
 120 static void gistnewroot(GISTSTATE *giststate, Relation r,
 121                         IndexTuple *itup, int len);
 122 static void GISTInitBuffer(Buffer b, uint32 f);
 123 static OffsetNumber gistchoose(Relation r, Page p,
 124                    IndexTuple it,
 125                    GISTSTATE *giststate);
 126 static void gistdelete(Relation r, ItemPointer tid);
 127
 128 #ifdef GIST_PAGEADDITEM
 129 static IndexTuple gist_tuple_replacekey(Relation r,
 130                                           GISTENTRY entry, IndexTuple t);
 131 #endif
 132 static void gistcentryinit(GISTSTATE *giststate, int nkey,
 133                            GISTENTRY *e, Datum k,
 134                            Relation r, Page pg,
 135                            OffsetNumber o, int b, bool l, bool isNull);
 136 static void gistDeCompressAtt(GISTSTATE *giststate, Relation r,
 137                                   IndexTuple tuple, Page p, OffsetNumber o,
 138                                   GISTENTRY attdata[], bool decompvec[], bool isnull[]);
 139 static void gistFreeAtt(Relation r, GISTENTRY attdata[], bool decompvec[]);
 140 static void gistpenalty(GISTSTATE *giststate, int attno,
 141                         GISTENTRY *key1, bool isNull1,
 142                         GISTENTRY *key2, bool isNull2,
 143                         float *penalty);
 144
 145 #undef GISTDEBUG
 146
 147 #ifdef GISTDEBUG
 148 static void gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff);
 149 #endif
 150
 151 /*
 152  * routine to build an index.  Basically calls insert over and over
 153  */
 154 Datum
 155 gistbuild(PG_FUNCTION_ARGS)
 156 {
 157         Relation        heap = (Relation) PG_GETARG_POINTER(0);
 158         Relation        index = (Relation) PG_GETARG_POINTER(1);
 159         IndexInfo  *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2);
 160         double          reltuples;
 161         GISTBuildState buildstate;
 162         Buffer          buffer;
 163
 164         /* no locking is needed */
 165
 166         initGISTstate(&buildstate.giststate, index);
 167
 168         /*
 169          * We expect to be called exactly once for any index relation. If
 170          * that's not the case, big trouble's what we have.
 171          */
 172         if (RelationGetNumberOfBlocks(index) != 0)
 173                 elog(ERROR, "%s already contains data",
 174                          RelationGetRelationName(index));
 175
 176         /* initialize the root page */
 177         buffer = ReadBuffer(index, P_NEW);
 178         GISTInitBuffer(buffer, F_LEAF);
 179         WriteBuffer(buffer);
 180
 181         /* build the index */
 182         buildstate.numindexattrs = indexInfo->ii_NumIndexAttrs;
 183         buildstate.indtuples = 0;
 184
 185         /* do the heap scan */
 186         reltuples = IndexBuildHeapScan(heap, index, indexInfo,
 187                                                                 gistbuildCallback, (void *) &buildstate);
 188
 189         /* okay, all heap tuples are indexed */
 190
 191         /*
 192          * Since we just counted the tuples in the heap, we update its stats
 193          * in pg_class to guarantee that the planner takes advantage of the
 194          * index we just created.  But, only update statistics during normal
 195          * index definitions, not for indices on system catalogs created
 196          * during bootstrap processing.  We must close the relations before
 197          * updating statistics to guarantee that the relcache entries are
 198          * flushed when we increment the command counter in UpdateStats(). But
 199          * we do not release any locks on the relations; those will be held
 200          * until end of transaction.
 201          */
 202         if (IsNormalProcessingMode())
 203         {
 204                 Oid                     hrelid = RelationGetRelid(heap);
 205                 Oid                     irelid = RelationGetRelid(index);
 206
 207                 heap_close(heap, NoLock);
 208                 index_close(index);
 209                 UpdateStats(hrelid, reltuples);
 210                 UpdateStats(irelid, buildstate.indtuples);
 211         }
 212
 213         freeGISTstate(&buildstate.giststate);
 214 #ifdef GISTDEBUG
 215         gist_dumptree(index, 0, GISTP_ROOT, 0);
 216 #endif
 217
 218         PG_RETURN_VOID();
 219 }
 220
 221 /*
 222  * Per-tuple callback from IndexBuildHeapScan
 223  */
 224 static void
 225 gistbuildCallback(Relation index,
 226                                   HeapTuple htup,
 227                                   Datum *attdata,
 228                                   char *nulls,
 229                                   bool tupleIsAlive,
 230                                   void *state)
 231 {
 232         GISTBuildState *buildstate = (GISTBuildState *) state;
 233         IndexTuple      itup;
 234         bool            compvec[INDEX_MAX_KEYS];
 235         GISTENTRY       tmpcentry;
 236         int                     i;
 237
 238         /* GiST cannot index tuples with leading NULLs */
 239         if (nulls[0] == 'n')
 240                 return;
 241
 242         /* immediately compress keys to normalize */
 243         for (i = 0; i < buildstate->numindexattrs; i++)
 244         {
 245                 if (nulls[i] == 'n')
 246                 {
 247                         attdata[i] = (Datum) 0;
 248                         compvec[i] = FALSE;
 249                 }
 250                 else
 251                 {
 252                         gistcentryinit(&buildstate->giststate, i, &tmpcentry, attdata[i],
 253                                                    (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
 254                                                  -1 /* size is currently bogus */ , TRUE, FALSE);
 255                         if (attdata[i] != tmpcentry.key &&
 256                                 !(isAttByVal(&buildstate->giststate, i)))
 257                                 compvec[i] = TRUE;
 258                         else
 259                                 compvec[i] = FALSE;
 260                         attdata[i] = tmpcentry.key;
 261                 }
 262         }
 263
 264         /* form an index tuple and point it at the heap tuple */
 265         itup = index_formtuple(buildstate->giststate.tupdesc, attdata, nulls);
 266         itup->t_tid = htup->t_self;
 267
 268         /*
 269          * Since we already have the index relation locked, we call
 270          * gistdoinsert directly.  Normal access method calls dispatch through
 271          * gistinsert, which locks the relation for write.      This is the right
 272          * thing to do if you're inserting single tups, but not when you're
 273          * initializing the whole index at once.
 274          */
 275         gistdoinsert(index, itup, NULL, &buildstate->giststate);
 276
 277         buildstate->indtuples += 1;
 278
 279         for (i = 0; i < buildstate->numindexattrs; i++)
 280                 if (compvec[i])
 281                         pfree(DatumGetPointer(attdata[i]));
 282
 283         pfree(itup);
 284 }
 285
 286 /*
 287  *      gistinsert -- wrapper for GiST tuple insertion.
 288  *
 289  *        This is the public interface routine for tuple insertion in GiSTs.
 290  *        It doesn't do any work; just locks the relation and passes the buck.
 291  */
 292 Datum
 293 gistinsert(PG_FUNCTION_ARGS)
 294 {
 295         Relation        r = (Relation) PG_GETARG_POINTER(0);
 296         Datum      *datum = (Datum *) PG_GETARG_POINTER(1);
 297         char       *nulls = (char *) PG_GETARG_POINTER(2);
 298         ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3);
 299
 300 #ifdef NOT_USED
 301         Relation        heapRel = (Relation) PG_GETARG_POINTER(4);
 302 #endif
 303         InsertIndexResult res;
 304         IndexTuple      itup;
 305         GISTSTATE       giststate;
 306         GISTENTRY       tmpentry;
 307         int                     i;
 308         bool            compvec[INDEX_MAX_KEYS];
 309
 310         /*
 311          * Since GIST is not marked "amconcurrent" in pg_am, caller should
 312          * have acquired exclusive lock on index relation.      We need no locking
 313          * here.
 314          */
 315
 316         /* GiST cannot index tuples with leading NULLs */
 317         if (nulls[0] == 'n')
 318         {
 319                 res = NULL;
 320                 PG_RETURN_POINTER(res);
 321         }
 322
 323         initGISTstate(&giststate, r);
 324
 325         /* immediately compress keys to normalize */
 326         for (i = 0; i < r->rd_att->natts; i++)
 327         {
 328                 if (nulls[i] == 'n')
 329                 {
 330                         datum[i] = (Datum) 0;
 331                         compvec[i] = FALSE;
 332                 }
 333                 else
 334                 {
 335                         gistcentryinit(&giststate, i, &tmpentry, datum[i],
 336                                                    (Relation) NULL, (Page) NULL, (OffsetNumber) 0,
 337                                                  -1 /* size is currently bogus */ , TRUE, FALSE);
 338                         if (datum[i] != tmpentry.key && !(isAttByVal(&giststate, i)))
 339                                 compvec[i] = TRUE;
 340                         else
 341                                 compvec[i] = FALSE;
 342                         datum[i] = tmpentry.key;
 343                 }
 344         }
 345         itup = index_formtuple(giststate.tupdesc, datum, nulls);
 346         itup->t_tid = *ht_ctid;
 347
 348         res = (InsertIndexResult) palloc(sizeof(InsertIndexResultData));
 349         gistdoinsert(r, itup, &res, &giststate);
 350
 351         for (i = 0; i < r->rd_att->natts; i++)
 352                 if (compvec[i] == TRUE)
 353                         pfree(DatumGetPointer(datum[i]));
 354         pfree(itup);
 355         freeGISTstate(&giststate);
 356
 357         PG_RETURN_POINTER(res);
 358 }
 359
 360 #ifdef GIST_PAGEADDITEM
 361 /*
 362 ** Take a compressed entry, and install it on a page.  Since we now know
 363 ** where the entry will live, we decompress it and recompress it using
 364 ** that knowledge (some compression routines may want to fish around
 365 ** on the page, for example, or do something special for leaf nodes.)
 366 */
 367 static OffsetNumber
 368 gistPageAddItem(GISTSTATE *giststate,
 369                                 Relation r,
 370                                 Page page,
 371                                 Item item,
 372                                 Size size,
 373                                 OffsetNumber offsetNumber,
 374                                 ItemIdFlags flags,
 375                                 GISTENTRY *dentry,
 376                                 IndexTuple *newtup)
 377 {
 378         GISTENTRY       tmpcentry;
 379         IndexTuple      itup = (IndexTuple) item;
 380         OffsetNumber retval;
 381         Datum           datum;
 382         bool            IsNull;
 383
 384         /*
 385          * recompress the item given that we now know the exact page and
 386          * offset for insertion
 387          */
 388         datum = index_getattr(itup, 1, r->rd_att, &IsNull);
 389         gistdentryinit(giststate, 0, dentry, datum,
 390                                    (Relation) 0, (Page) 0,
 391                                    (OffsetNumber) InvalidOffsetNumber,
 392                                    ATTSIZE(datum, r, 1, IsNull),
 393                                    FALSE, IsNull);
 394         gistcentryinit(giststate, 0, &tmpcentry, dentry->key, r, page,
 395                                    offsetNumber, dentry->bytes, FALSE);
 396         *newtup = gist_tuple_replacekey(r, tmpcentry, itup);
 397         retval = PageAddItem(page, (Item) *newtup, IndexTupleSize(*newtup),
 398                                                  offsetNumber, flags);
 399         if (retval == InvalidOffsetNumber)
 400                 elog(ERROR, "gist: failed to add index item to %s",
 401                          RelationGetRelationName(r));
 402         /* be tidy */
 403         if (DatumGetPointer(tmpcentry.key) != NULL &&
 404                 tmpcentry.key != dentry->key &&
 405                 tmpcentry.key != datum)
 406                 pfree(DatumGetPointer(tmpcentry.key));
 407         return (retval);
 408 }
 409 #endif
 410
 411 static void
 412 gistdoinsert(Relation r,
 413                          IndexTuple itup,
 414                          InsertIndexResult *res,
 415                          GISTSTATE *giststate)
 416 {
 417         IndexTuple *instup;
 418         int                     i,
 419                                 ret,
 420                                 len = 1;
 421
 422         instup = (IndexTuple *) palloc(sizeof(IndexTuple));
 423         instup[0] = (IndexTuple) palloc(IndexTupleSize(itup));
 424         memcpy(instup[0], itup, IndexTupleSize(itup));
 425
 426         ret = gistlayerinsert(r, GISTP_ROOT, &instup, &len, res, giststate);
 427         if (ret & SPLITED)
 428                 gistnewroot(giststate, r, instup, len);
 429
 430         for (i = 0; i < len; i++)
 431                 pfree(instup[i]);
 432         pfree(instup);
 433 }
 434
 435 static int
 436 gistlayerinsert(Relation r, BlockNumber blkno,
 437                                 IndexTuple **itup,              /* in - out, has compressed entry */
 438                                 int *len,               /* in - out */
 439                                 InsertIndexResult *res, /* out */
 440                                 GISTSTATE *giststate)
 441 {
 442         Buffer          buffer;
 443         Page            page;
 444         OffsetNumber child;
 445         int                     ret;
 446         GISTPageOpaque opaque;
 447
 448         buffer = ReadBuffer(r, blkno);
 449         page = (Page) BufferGetPage(buffer);
 450         opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
 451
 452         if (!(opaque->flags & F_LEAF))
 453         {
 454                 /* internal page, so we must walk on tree */
 455                 /* len IS equial 1 */
 456                 ItemId          iid;
 457                 BlockNumber nblkno;
 458                 ItemPointerData oldtid;
 459                 IndexTuple      oldtup;
 460
 461                 child = gistchoose(r, page, *(*itup), giststate);
 462                 iid = PageGetItemId(page, child);
 463                 oldtup = (IndexTuple) PageGetItem(page, iid);
 464                 nblkno = ItemPointerGetBlockNumber(&(oldtup->t_tid));
 465
 466                 /*
 467                  * After this call: 1. if child page was splited, then itup
 468                  * contains keys for each page 2. if  child page wasn't splited,
 469                  * then itup contains additional for adjustement of current key
 470                  */
 471                 ret = gistlayerinsert(r, nblkno, itup, len, res, giststate);
 472
 473                 /* nothing inserted in child */
 474                 if (!(ret & INSERTED))
 475                 {
 476                         ReleaseBuffer(buffer);
 477                         return 0x00;
 478                 }
 479
 480                 /* child does not splited */
 481                 if (!(ret & SPLITED))
 482                 {
 483                         IndexTuple      newtup = gistgetadjusted(r, oldtup, (*itup)[0], giststate);
 484
 485                         if (!newtup)
 486                         {
 487                                 /* not need to update key */
 488                                 ReleaseBuffer(buffer);
 489                                 return 0x00;
 490                         }
 491
 492                         pfree((*itup)[0]);      /* !!! */
 493                         (*itup)[0] = newtup;
 494                 }
 495
 496                 /* key is modified, so old version must be deleted */
 497                 ItemPointerSet(&oldtid, blkno, child);
 498                 gistdelete(r, &oldtid);
 499         }
 500
 501         ret = INSERTED;
 502
 503         if (gistnospace(page, (*itup), *len))
 504         {
 505                 /* no space for insertion */
 506                 IndexTuple *itvec,
 507                                    *newitup;
 508                 int                     tlen,
 509                                         oldlen;
 510
 511                 ret |= SPLITED;
 512                 itvec = gistreadbuffer(r, buffer, &tlen);
 513                 itvec = gistjoinvector(itvec, &tlen, (*itup), *len);
 514                 oldlen = *len;
 515                 newitup = gistSplit(r, buffer, itvec, &tlen, giststate,
 516                                                         (opaque->flags & F_LEAF) ? res : NULL);         /* res only for
 517                                                                                                                                                  * inserting in leaf */
 518                 ReleaseBuffer(buffer);
 519                 do
 520                         pfree((*itup)[oldlen - 1]);
 521                 while ((--oldlen) > 0);
 522                 pfree((*itup));
 523                 pfree(itvec);
 524                 *itup = newitup;
 525                 *len = tlen;                    /* now tlen >= 2 */
 526         }
 527         else
 528         {
 529                 /* enogth space */
 530                 OffsetNumber off,
 531                                         l;
 532
 533                 off = (PageIsEmpty(page)) ?
 534                         FirstOffsetNumber
 535                         :
 536                         OffsetNumberNext(PageGetMaxOffsetNumber(page));
 537                 l = gistwritebuffer(r, page, (*itup), *len, off, giststate);
 538                 WriteBuffer(buffer);
 539
 540                 /*
 541                  * set res if insert into leaf page, in this case, len = 1 always
 542                  */
 543                 if (res && (opaque->flags & F_LEAF))
 544                         ItemPointerSet(&((*res)->pointerData), blkno, l);
 545
 546                 if (*len > 1)
 547                 {                                               /* previos insert ret & SPLITED != 0 */
 548                         int                     i;
 549
 550                         /*
 551                          * child was splited, so we must form union for insertion in
 552                          * parent
 553                          */
 554                         IndexTuple      newtup = gistunion(r, (*itup), *len, giststate);
 555
 556                         ItemPointerSet(&(newtup->t_tid), blkno, 1);
 557
 558                         for (i = 0; i < *len; i++)
 559                                 pfree((*itup)[i]);
 560                         (*itup)[0] = newtup;
 561                         *len = 1;
 562                 }
 563         }
 564
 565         return ret;
 566 }
 567
 568 /*
 569  * Write itup vector to page, has no control of free space
 570  */
 571 static OffsetNumber
 572 gistwritebuffer(Relation r, Page page, IndexTuple *itup,
 573                                 int len, OffsetNumber off, GISTSTATE *giststate)
 574 {
 575         OffsetNumber l = InvalidOffsetNumber;
 576         int                     i;
 577
 578 #ifdef GIST_PAGEADDITEM
 579         GISTENTRY       tmpdentry;
 580         IndexTuple      newtup;
 581         bool            IsNull;
 582 #endif
 583         for (i = 0; i < len; i++)
 584         {
 585 #ifdef GIST_PAGEADDITEM
 586                 l = gistPageAddItem(giststate, r, page,
 587                                                         (Item) itup[i], IndexTupleSize(itup[i]),
 588                                                         off, LP_USED, &tmpdentry, &newtup);
 589                 off = OffsetNumberNext(off);
 590                 if (DatumGetPointer(tmpdentry.key) != NULL &&
 591                   tmpdentry.key != index_getattr(itup[i], 1, r->rd_att, &IsNull))
 592                         pfree(DatumGetPointer(tmpdentry.key));
 593                 if (itup[i] != newtup)
 594                         pfree(newtup);
 595 #else
 596                 l = PageAddItem(page, (Item) itup[i], IndexTupleSize(itup[i]),
 597                                                 off, LP_USED);
 598                 if (l == InvalidOffsetNumber)
 599                         elog(ERROR, "gist: failed to add index item to %s",
 600                                  RelationGetRelationName(r));
 601 #endif
 602         }
 603         return l;
 604 }
 605
 606 /*
 607  * Check space for itup vector on page
 608  */
 609 static int
 610 gistnospace(Page page, IndexTuple *itvec, int len)
 611 {
 612         int                     size = 0;
 613         int                     i;
 614
 615         for (i = 0; i < len; i++)
 616                 size += IndexTupleSize(itvec[i]) + sizeof(ItemIdData);
 617
 618         return (PageGetFreeSpace(page) < size);
 619 }
 620
 621 /*
 622  * Read buffer into itup vector
 623  */
 624 static IndexTuple *
 625 gistreadbuffer(Relation r, Buffer buffer, int *len /* out */ )
 626 {
 627         OffsetNumber i,
 628                                 maxoff;
 629         IndexTuple *itvec;
 630         Page            p = (Page) BufferGetPage(buffer);
 631
 632         maxoff = PageGetMaxOffsetNumber(p);
 633         *len = maxoff;
 634         itvec = palloc(sizeof(IndexTuple) * maxoff);
 635         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 636                 itvec[i - 1] = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
 637
 638         return itvec;
 639 }
 640
 641 /*
 642  * join two vectors into one
 643  */
 644 static IndexTuple *
 645 gistjoinvector(IndexTuple *itvec, int *len, IndexTuple *additvec, int addlen)
 646 {
 647         itvec = (IndexTuple *) repalloc((void *) itvec, sizeof(IndexTuple) * ((*len) + addlen));
 648         memmove(&itvec[*len], additvec, sizeof(IndexTuple) * addlen);
 649         *len += addlen;
 650         return itvec;
 651 }
 652
 653 /*
 654  * return union of itup vector
 655  */
 656 static IndexTuple
 657 gistunion(Relation r, IndexTuple *itvec, int len, GISTSTATE *giststate)
 658 {
 659         Datum           attr[INDEX_MAX_KEYS];
 660         bool            whatfree[INDEX_MAX_KEYS];
 661         char            isnull[INDEX_MAX_KEYS];
 662         char       *storage;
 663         bytea      *evec;
 664         Datum           datum;
 665         int                     datumsize,
 666                                 i,
 667                                 j;
 668         GISTENTRY       centry[INDEX_MAX_KEYS];
 669         bool       *needfree;
 670         IndexTuple      newtup;
 671         bool            IsNull;
 672         int                     reallen;
 673
 674         needfree = (bool *) palloc(((len == 1) ? 2 : len) * sizeof(bool));
 675         /* workaround for 64-bit: ensure GISTENTRY array is maxaligned */
 676         storage = (char*)palloc( ((len == 1) ? 2 : len) * sizeof(GISTENTRY) + MAXALIGN(VARHDRSZ));
 677         evec = (bytea *) (storage + MAXALIGN(VARHDRSZ) - VARHDRSZ);
 678
 679         for (j = 0; j < r->rd_att->natts; j++)
 680         {
 681                 reallen = 0;
 682                 for (i = 0; i < len; i++)
 683                 {
 684                         datum = index_getattr(itvec[i], j + 1, giststate->tupdesc, &IsNull);
 685                         if (IsNull)
 686                                 continue;
 687
 688                         gistdentryinit(giststate, j,
 689                                                    &((GISTENTRY *) VARDATA(evec))[reallen],
 690                                                    datum,
 691                                            (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
 692                                                    ATTSIZE(datum, giststate->tupdesc, j + 1, IsNull), FALSE, IsNull);
 693                         if ((!isAttByVal(giststate, j)) &&
 694                                 ((GISTENTRY *) VARDATA(evec))[reallen].key != datum)
 695                                 needfree[reallen] = TRUE;
 696                         else
 697                                 needfree[reallen] = FALSE;
 698                         reallen++;
 699                 }
 700
 701                 if (reallen == 0)
 702                 {
 703                         attr[j] = (Datum) 0;
 704                         isnull[j] = 'n';
 705                         whatfree[j] = FALSE;
 706                 }
 707                 else
 708                 {
 709                         if (reallen == 1)
 710                         {
 711                                 VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
 712                                 gistentryinit(((GISTENTRY *) VARDATA(evec))[1],
 713                                         ((GISTENTRY *) VARDATA(evec))[0].key, r, (Page) NULL,
 714                                                           (OffsetNumber) 0, ((GISTENTRY *) VARDATA(evec))[0].bytes, FALSE);
 715
 716                         }
 717                         else
 718                                 VARATT_SIZEP(evec) = reallen * sizeof(GISTENTRY) + VARHDRSZ;
 719                         datum = FunctionCall2(&giststate->unionFn[j],
 720                                                                   PointerGetDatum(evec),
 721                                                                   PointerGetDatum(&datumsize));
 722
 723                         for (i = 0; i < reallen; i++)
 724                                 if (needfree[i])
 725                                         pfree(DatumGetPointer(((GISTENTRY *) VARDATA(evec))[i].key));
 726
 727                         gistcentryinit(giststate, j, &centry[j], datum,
 728                                            (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
 729                                                    datumsize, FALSE, FALSE);
 730                         isnull[j] = ' ';
 731                         attr[j] = centry[j].key;
 732                         if (!isAttByVal(giststate, j))
 733                         {
 734                                 whatfree[j] = TRUE;
 735                                 if (centry[j].key != datum)
 736                                         pfree(DatumGetPointer(datum));
 737                         }
 738                         else
 739                                 whatfree[j] = FALSE;
 740                 }
 741         }
 742
 743         pfree(storage);                         /* pfree(evec); */
 744         pfree(needfree);
 745
 746         newtup = (IndexTuple) index_formtuple(giststate->tupdesc, attr, isnull);
 747         for (j = 0; j < r->rd_att->natts; j++)
 748                 if (whatfree[j])
 749                         pfree(DatumGetPointer(attr[j]));
 750
 751         return newtup;
 752 }
 753
 754
 755 /*
 756  * Forms union of oldtup and addtup, if union == oldtup then return NULL
 757  */
 758 static IndexTuple
 759 gistgetadjusted(Relation r, IndexTuple oldtup, IndexTuple addtup, GISTSTATE *giststate)
 760 {
 761         bytea      *evec;
 762         Datum           datum;
 763         int                     datumsize;
 764         bool            result,
 765                                 neednew = false;
 766         char            isnull[INDEX_MAX_KEYS],
 767                                 whatfree[INDEX_MAX_KEYS];
 768         Datum           attr[INDEX_MAX_KEYS];
 769         GISTENTRY       centry[INDEX_MAX_KEYS],
 770                                 oldatt[INDEX_MAX_KEYS],
 771                                 addatt[INDEX_MAX_KEYS],
 772                            *ev0p,
 773                            *ev1p;
 774         bool            olddec[INDEX_MAX_KEYS],
 775                                 adddec[INDEX_MAX_KEYS];
 776         bool            oldisnull[INDEX_MAX_KEYS],
 777                                 addisnull[INDEX_MAX_KEYS];
 778         IndexTuple      newtup = NULL;
 779         char       *storage;
 780         int                     j;
 781
 782         /* workaround for 64-bit: ensure GISTENTRY array is maxaligned */
 783         storage = (char*) palloc( 2 * sizeof(GISTENTRY) + MAXALIGN(VARHDRSZ));
 784         evec = (bytea *) (storage + MAXALIGN(VARHDRSZ) - VARHDRSZ);
 785         VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
 786         ev0p = &((GISTENTRY *) VARDATA(evec))[0];
 787         ev1p = &((GISTENTRY *) VARDATA(evec))[1];
 788
 789         gistDeCompressAtt(giststate, r, oldtup, (Page) NULL,
 790                                           (OffsetNumber) 0, oldatt, olddec, oldisnull);
 791
 792         gistDeCompressAtt(giststate, r, addtup, (Page) NULL,
 793                                           (OffsetNumber) 0, addatt, adddec, addisnull);
 794
 795
 796         for (j = 0; j < r->rd_att->natts; j++)
 797         {
 798                 if (oldisnull[j] && addisnull[j])
 799                 {
 800                         isnull[j] = 'n';
 801                         attr[j] = (Datum) 0;
 802                         whatfree[j] = FALSE;
 803                 }
 804                 else
 805                 {
 806                         FILLEV(
 807                                    oldisnull[j], oldatt[j].key, oldatt[j].bytes,
 808                                    addisnull[j], addatt[j].key, addatt[j].bytes
 809                                 );
 810
 811                         datum = FunctionCall2(&giststate->unionFn[j],
 812                                                                   PointerGetDatum(evec),
 813                                                                   PointerGetDatum(&datumsize));
 814
 815                         if (oldisnull[j] || addisnull[j])
 816                         {
 817                                 if (oldisnull[j])
 818                                         neednew = true;
 819                         }
 820                         else
 821                         {
 822                                 FunctionCall3(&giststate->equalFn[j],
 823                                                           ev0p->key,
 824                                                           datum,
 825                                                           PointerGetDatum(&result));
 826
 827                                 if (!result)
 828                                         neednew = true;
 829                         }
 830
 831                         if (olddec[j])
 832                                 pfree(DatumGetPointer(oldatt[j].key));
 833                         if (adddec[j])
 834                                 pfree(DatumGetPointer(addatt[j].key));
 835
 836                         gistcentryinit(giststate, j, &centry[j], datum,
 837                                            (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
 838                                                    datumsize, FALSE, FALSE);
 839
 840                         isnull[j] = ' ';
 841                         attr[j] = centry[j].key;
 842                         if ((!isAttByVal(giststate, j)))
 843                         {
 844                                 whatfree[j] = TRUE;
 845                                 if (centry[j].key != datum)
 846                                         pfree(DatumGetPointer(datum));
 847                         }
 848                         else
 849                                 whatfree[j] = FALSE;
 850                 }
 851         }
 852         pfree(storage);                         /* pfree(evec); */
 853
 854         if (neednew)
 855         {
 856                 /* need to update key */
 857                 newtup = (IndexTuple) index_formtuple(giststate->tupdesc, attr, isnull);
 858                 newtup->t_tid = oldtup->t_tid;
 859         }
 860
 861         for (j = 0; j < r->rd_att->natts; j++)
 862                 if (whatfree[j])
 863                         pfree(DatumGetPointer(attr[j]));
 864
 865         return newtup;
 866 }
 867
 868 static void
 869 gistunionsubkey(Relation r, GISTSTATE *giststate, IndexTuple *itvec, GIST_SPLITVEC *spl)
 870 {
 871         int                     i,
 872                                 j,
 873                                 lr;
 874         Datum      *attr;
 875         bool       *needfree,
 876                                 IsNull;
 877         int                     len,
 878                            *attrsize;
 879         OffsetNumber *entries;
 880         bytea      *evec;
 881         char       *storage;
 882         Datum           datum;
 883         int                     datumsize;
 884         int                     reallen;
 885         bool       *isnull;
 886
 887         for (lr = 0; lr <= 1; lr++)
 888         {
 889                 if (lr)
 890                 {
 891                         attrsize = spl->spl_lattrsize;
 892                         attr = spl->spl_lattr;
 893                         len = spl->spl_nleft;
 894                         entries = spl->spl_left;
 895                         isnull = spl->spl_lisnull;
 896                 }
 897                 else
 898                 {
 899                         attrsize = spl->spl_rattrsize;
 900                         attr = spl->spl_rattr;
 901                         len = spl->spl_nright;
 902                         entries = spl->spl_right;
 903                         isnull = spl->spl_risnull;
 904                 }
 905
 906                 needfree = (bool *) palloc(((len == 1) ? 2 : len) * sizeof(bool));
 907                 /* workaround for 64-bit: ensure GISTENTRY array is maxaligned */
 908                 storage = (char*)palloc( ((len == 1) ? 2 : len) * sizeof(GISTENTRY) + MAXALIGN(VARHDRSZ));
 909                 evec = (bytea *) (storage + MAXALIGN(VARHDRSZ) - VARHDRSZ);
 910
 911                 for (j = 1; j < r->rd_att->natts; j++)
 912                 {
 913                         reallen = 0;
 914                         for (i = 0; i < len; i++)
 915                         {
 916                                 if (spl->spl_idgrp[entries[i]])
 917                                         continue;
 918                                 datum = index_getattr(itvec[entries[i] - 1], j + 1,
 919                                                                           giststate->tupdesc, &IsNull);
 920                                 if (IsNull)
 921                                         continue;
 922                                 gistdentryinit(giststate, j,
 923                                                            &((GISTENTRY *) VARDATA(evec))[reallen],
 924                                                            datum,
 925                                                            (Relation) NULL, (Page) NULL,
 926                                                            (OffsetNumber) NULL,
 927                                                            ATTSIZE(datum, giststate->tupdesc, j + 1, IsNull), FALSE, IsNull);
 928                                 if ((!isAttByVal(giststate, j)) &&
 929                                         ((GISTENTRY *) VARDATA(evec))[reallen].key != datum)
 930                                         needfree[reallen] = TRUE;
 931                                 else
 932                                         needfree[reallen] = FALSE;
 933                                 reallen++;
 934
 935                         }
 936                         if (reallen == 0)
 937                         {
 938                                 datum = (Datum) 0;
 939                                 datumsize = 0;
 940                                 isnull[j] = true;
 941                         }
 942                         else
 943                         {
 944                                 /*
 945                                  * ((GISTENTRY *) VARDATA(evec))[0].bytes may be not
 946                                  * defined, so form union with itself
 947                                  */
 948                                 if (reallen == 1)
 949                                 {
 950                                         VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
 951                                         memcpy((void *) &((GISTENTRY *) VARDATA(evec))[1],
 952                                                    (void *) &((GISTENTRY *) VARDATA(evec))[0],
 953                                                    sizeof(GISTENTRY));
 954                                 }
 955                                 else
 956                                         VARATT_SIZEP(evec) = reallen * sizeof(GISTENTRY) + VARHDRSZ;
 957                                 datum = FunctionCall2(&giststate->unionFn[j],
 958                                                                           PointerGetDatum(evec),
 959                                                                           PointerGetDatum(&datumsize));
 960                                 isnull[j] = false;
 961                         }
 962
 963                         for (i = 0; i < reallen; i++)
 964                                 if (needfree[i])
 965                                         pfree(DatumGetPointer(((GISTENTRY *) VARDATA(evec))[i].key));
 966
 967                         attr[j] = datum;
 968                         attrsize[j] = datumsize;
 969                 }
 970                 pfree(storage);                 /* pfree(evec); */
 971                 pfree(needfree);
 972         }
 973 }
 974
 975 /*
 976  * find group in vector with equial value
 977  */
 978 static int
 979 gistfindgroup(GISTSTATE *giststate, GISTENTRY *valvec, GIST_SPLITVEC *spl)
 980 {
 981         int                     i,
 982                                 j,
 983                                 len;
 984         int                     curid = 1;
 985         bool            result;
 986
 987         /*
 988          * first key is always not null (see gistinsert), so we may not check
 989          * for nulls
 990          */
 991
 992         for (i = 0; i < spl->spl_nleft; i++)
 993         {
 994                 if (spl->spl_idgrp[spl->spl_left[i]])
 995                         continue;
 996                 len = 0;
 997                 /* find all equal value in right part */
 998                 for (j = 0; j < spl->spl_nright; j++)
 999                 {
1000                         if (spl->spl_idgrp[spl->spl_right[j]])
1001                                 continue;
1002                         FunctionCall3(&giststate->equalFn[0],
1003                                                   valvec[spl->spl_left[i]].key,
1004                                                   valvec[spl->spl_right[j]].key,
1005                                                   PointerGetDatum(&result));
1006                         if (result)
1007                         {
1008                                 spl->spl_idgrp[spl->spl_right[j]] = curid;
1009                                 len++;
1010                         }
1011                 }
1012                 /* find all other equal value in left part */
1013                 if (len)
1014                 {
1015                         /* add current val to list of equial values */
1016                         spl->spl_idgrp[spl->spl_left[i]] = curid;
1017                         /* searching .. */
1018                         for (j = i + 1; j < spl->spl_nleft; j++)
1019                         {
1020                                 if (spl->spl_idgrp[spl->spl_left[j]])
1021                                         continue;
1022                                 FunctionCall3(&giststate->equalFn[0],
1023                                                           valvec[spl->spl_left[i]].key,
1024                                                           valvec[spl->spl_left[j]].key,
1025                                                           PointerGetDatum(&result));
1026                                 if (result)
1027                                 {
1028                                         spl->spl_idgrp[spl->spl_left[j]] = curid;
1029                                         len++;
1030                                 }
1031                         }
1032                         spl->spl_ngrp[curid] = len + 1;
1033                         curid++;
1034                 }
1035         }
1036
1037         return curid;
1038 }
1039
1040 /*
1041  * Insert equivalent tuples to left or right page
1042  * with minimize penalty
1043  */
1044 static void
1045 gistadjsubkey(Relation r,
1046                           IndexTuple *itup, /* contains compressed entry */
1047                           int *len,
1048                           GIST_SPLITVEC *v,
1049                           GISTSTATE *giststate
1050 )
1051 {
1052         int                     curlen;
1053         OffsetNumber *curwpos;
1054         bool            decfree[INDEX_MAX_KEYS];
1055         GISTENTRY       entry,
1056                                 identry[INDEX_MAX_KEYS],
1057                            *ev0p,
1058                            *ev1p;
1059         float           lpenalty,
1060                                 rpenalty;
1061         bytea      *evec;
1062         char       *storage;
1063         int                     datumsize;
1064         bool            isnull[INDEX_MAX_KEYS];
1065         int                     i,
1066                                 j;
1067         Datum           datum;
1068
1069         /* clear vectors */
1070         curlen = v->spl_nleft;
1071         curwpos = v->spl_left;
1072         for (i = 0; i < v->spl_nleft; i++)
1073                 if (v->spl_idgrp[v->spl_left[i]] == 0)
1074                 {
1075                         *curwpos = v->spl_left[i];
1076                         curwpos++;
1077                 }
1078                 else
1079                         curlen--;
1080         v->spl_nleft = curlen;
1081
1082         curlen = v->spl_nright;
1083         curwpos = v->spl_right;
1084         for (i = 0; i < v->spl_nright; i++)
1085                 if (v->spl_idgrp[v->spl_right[i]] == 0)
1086                 {
1087                         *curwpos = v->spl_right[i];
1088                         curwpos++;
1089                 }
1090                 else
1091                         curlen--;
1092         v->spl_nright = curlen;
1093
1094         /* workaround for 64-bit: ensure GISTENTRY array is maxaligned */
1095         storage = (char*)palloc( 2 * sizeof(GISTENTRY) + MAXALIGN(VARHDRSZ));
1096         evec = (bytea *) (storage + MAXALIGN(VARHDRSZ) - VARHDRSZ);
1097         VARATT_SIZEP(evec) = 2 * sizeof(GISTENTRY) + VARHDRSZ;
1098         ev0p = &((GISTENTRY *) VARDATA(evec))[0];
1099         ev1p = &((GISTENTRY *) VARDATA(evec))[1];
1100
1101         /* add equivalent tuple */
1102         for (i = 0; i < *len; i++)
1103         {
1104                 if (v->spl_idgrp[i + 1] == 0)   /* already inserted */
1105                         continue;
1106                 gistDeCompressAtt(giststate, r, itup[i], (Page) NULL, (OffsetNumber) 0,
1107                                                   identry, decfree, isnull);
1108
1109                 v->spl_ngrp[v->spl_idgrp[i + 1]]--;
1110                 if (v->spl_ngrp[v->spl_idgrp[i + 1]] == 0 &&
1111                 (v->spl_grpflag[v->spl_idgrp[i + 1]] & BOTH_ADDED) != BOTH_ADDED)
1112                 {
1113
1114                         /* force last in group */
1115                         rpenalty = 1.0;
1116                         lpenalty = (v->spl_grpflag[v->spl_idgrp[i + 1]] & LEFT_ADDED) ? 2.0 : 0.0;
1117                 }
1118                 else
1119                 {
1120                         /* where? */
1121                         for (j = 1; j < r->rd_att->natts; j++)
1122                         {
1123                                 gistentryinit(entry, v->spl_lattr[j], r, (Page) NULL,
1124                                                    (OffsetNumber) 0, v->spl_lattrsize[j], FALSE);
1125                                 gistpenalty(giststate, j, &entry, v->spl_lisnull[j],
1126                                                         &identry[j], isnull[j], &lpenalty);
1127
1128                                 gistentryinit(entry, v->spl_rattr[j], r, (Page) NULL,
1129                                                    (OffsetNumber) 0, v->spl_rattrsize[j], FALSE);
1130                                 gistpenalty(giststate, j, &entry, v->spl_risnull[j],
1131                                                         &identry[j], isnull[j], &rpenalty);
1132
1133                                 if (lpenalty != rpenalty)
1134                                         break;
1135                         }
1136                 }
1137                 /* add */
1138                 if (lpenalty < rpenalty)
1139                 {
1140                         v->spl_grpflag[v->spl_idgrp[i + 1]] |= LEFT_ADDED;
1141                         v->spl_left[v->spl_nleft] = i + 1;
1142                         v->spl_nleft++;
1143                         for (j = 1; j < r->rd_att->natts; j++)
1144                         {
1145                                 if (isnull[j] && v->spl_lisnull[j])
1146                                 {
1147                                         v->spl_lattr[j] = (Datum) 0;
1148                                         v->spl_lattrsize[j] = 0;
1149                                 }
1150                                 else
1151                                 {
1152                                         FILLEV(
1153                                                    v->spl_lisnull[j], v->spl_lattr[j], v->spl_lattrsize[j],
1154                                                    isnull[j], identry[j].key, identry[j].bytes
1155                                                 );
1156
1157                                         datum = FunctionCall2(&giststate->unionFn[j],
1158                                                                                   PointerGetDatum(evec),
1159                                                                                   PointerGetDatum(&datumsize));
1160
1161                                         if ((!isAttByVal(giststate, j)) && !v->spl_lisnull[j])
1162                                                 pfree(DatumGetPointer(v->spl_lattr[j]));
1163                                         v->spl_lattr[j] = datum;
1164                                         v->spl_lattrsize[j] = datumsize;
1165                                         v->spl_lisnull[j] = false;
1166                                 }
1167                         }
1168                 }
1169                 else
1170                 {
1171                         v->spl_grpflag[v->spl_idgrp[i + 1]] |= RIGHT_ADDED;
1172                         v->spl_right[v->spl_nright] = i + 1;
1173                         v->spl_nright++;
1174                         for (j = 1; j < r->rd_att->natts; j++)
1175                         {
1176                                 if (isnull[j] && v->spl_risnull[j])
1177                                 {
1178                                         v->spl_rattr[j] = (Datum) 0;
1179                                         v->spl_rattrsize[j] = 0;
1180                                 }
1181                                 else
1182                                 {
1183                                         FILLEV(
1184                                                    v->spl_risnull[j], v->spl_rattr[j], v->spl_rattrsize[j],
1185                                                    isnull[j], identry[j].key, identry[j].bytes
1186                                                 );
1187
1188                                         datum = FunctionCall2(&giststate->unionFn[j],
1189                                                                                   PointerGetDatum(evec),
1190                                                                                   PointerGetDatum(&datumsize));
1191
1192                                         if ((!isAttByVal(giststate, j)) && !v->spl_risnull[j])
1193                                                 pfree(DatumGetPointer(v->spl_rattr[j]));
1194
1195                                         v->spl_rattr[j] = datum;
1196                                         v->spl_rattrsize[j] = datumsize;
1197                                         v->spl_risnull[j] = false;
1198                                 }
1199                         }
1200
1201                 }
1202                 gistFreeAtt(r, identry, decfree);
1203         }
1204         pfree(storage);                         /* pfree(evec); */
1205 }
1206
1207 /*
1208  *      gistSplit -- split a page in the tree.
1209  */
1210 static IndexTuple *
1211 gistSplit(Relation r,
1212                   Buffer buffer,
1213                   IndexTuple *itup,             /* contains compressed entry */
1214                   int *len,
1215                   GISTSTATE *giststate,
1216                   InsertIndexResult *res)
1217 {
1218         Page            p;
1219         Buffer          leftbuf,
1220                                 rightbuf;
1221         Page            left,
1222                                 right;
1223         IndexTuple *lvectup,
1224                            *rvectup,
1225                            *newtup;
1226         BlockNumber lbknum,
1227                                 rbknum;
1228         GISTPageOpaque opaque;
1229         GIST_SPLITVEC v;
1230         bytea      *entryvec;
1231         char       *storage;
1232         bool       *decompvec;
1233         int                     i,
1234                                 j,
1235                                 nlen;
1236         int                     MaxGrpId = 1;
1237         Datum           datum;
1238         bool            IsNull;
1239
1240         p = (Page) BufferGetPage(buffer);
1241         opaque = (GISTPageOpaque) PageGetSpecialPointer(p);
1242
1243         /*
1244          * The root of the tree is the first block in the relation.  If we're
1245          * about to split the root, we need to do some hocus-pocus to enforce
1246          * this guarantee.
1247          */
1248
1249         if (BufferGetBlockNumber(buffer) == GISTP_ROOT)
1250         {
1251                 leftbuf = ReadBuffer(r, P_NEW);
1252                 GISTInitBuffer(leftbuf, opaque->flags);
1253                 lbknum = BufferGetBlockNumber(leftbuf);
1254                 left = (Page) BufferGetPage(leftbuf);
1255         }
1256         else
1257         {
1258                 leftbuf = buffer;
1259                 IncrBufferRefCount(buffer);
1260                 lbknum = BufferGetBlockNumber(buffer);
1261                 left = (Page) PageGetTempPage(p, sizeof(GISTPageOpaqueData));
1262         }
1263
1264         rightbuf = ReadBuffer(r, P_NEW);
1265         GISTInitBuffer(rightbuf, opaque->flags);
1266         rbknum = BufferGetBlockNumber(rightbuf);
1267         right = (Page) BufferGetPage(rightbuf);
1268
1269         /* generate the item array */
1270         /* workaround for 64-bit: ensure GISTENTRY array is maxaligned */
1271         storage = palloc(MAXALIGN(VARHDRSZ) + (*len + 1) * sizeof(GISTENTRY));
1272         entryvec = (bytea *) (storage + MAXALIGN(VARHDRSZ) - VARHDRSZ);
1273         decompvec = (bool *) palloc( (*len + 1) * sizeof(bool));
1274         VARATT_SIZEP(entryvec) = (*len + 1) * sizeof(GISTENTRY) + VARHDRSZ;
1275         for (i = 1; i <= *len; i++)
1276         {
1277                 datum = index_getattr(itup[i - 1], 1, giststate->tupdesc, &IsNull);
1278                 gistdentryinit(giststate, 0, &((GISTENTRY *) VARDATA(entryvec))[i],
1279                                            datum, r, p, i,
1280                    ATTSIZE(datum, giststate->tupdesc, 1, IsNull), FALSE, IsNull);
1281                 if ((!isAttByVal(giststate, 0)) && ((GISTENTRY *) VARDATA(entryvec))[i].key != datum)
1282                         decompvec[i] = TRUE;
1283                 else
1284                         decompvec[i] = FALSE;
1285         }
1286
1287         /*
1288          * now let the user-defined picksplit function set up the split
1289          * vector; in entryvec have no null value!!
1290          */
1291         FunctionCall2(&giststate->picksplitFn[0],
1292                                   PointerGetDatum(entryvec),
1293                                   PointerGetDatum(&v));
1294
1295         /* compatibility with old code */
1296         if (v.spl_left[v.spl_nleft - 1] == InvalidOffsetNumber)
1297                 v.spl_left[v.spl_nleft - 1] = (OffsetNumber) *len;
1298         if (v.spl_right[v.spl_nright - 1] == InvalidOffsetNumber)
1299                 v.spl_right[v.spl_nright - 1] = (OffsetNumber) *len;
1300
1301         v.spl_lattr[0] = v.spl_ldatum;
1302         v.spl_rattr[0] = v.spl_rdatum;
1303         v.spl_lisnull[0] = false;
1304         v.spl_risnull[0] = false;
1305
1306         /*
1307          * if index is multikey, then we must to try get smaller bounding box
1308          * for subkey(s)
1309          */
1310         if (r->rd_att->natts > 1)
1311         {
1312                 v.spl_idgrp = (int *) palloc(sizeof(int) * (*len + 1));
1313                 MemSet((void *) v.spl_idgrp, 0, sizeof(int) * (*len + 1));
1314                 v.spl_grpflag = (char *) palloc(sizeof(char) * (*len + 1));
1315                 MemSet((void *) v.spl_grpflag, 0, sizeof(char) * (*len + 1));
1316                 v.spl_ngrp = (int *) palloc(sizeof(int) * (*len + 1));
1317
1318                 MaxGrpId = gistfindgroup(giststate, (GISTENTRY *) VARDATA(entryvec), &v);
1319
1320                 /* form union of sub keys for each page (l,p) */
1321                 gistunionsubkey(r, giststate, itup, &v);
1322
1323                 /*
1324                  * if possible, we insert equivalent tuples with control by
1325                  * penalty for a subkey(s)
1326                  */
1327                 if (MaxGrpId > 1)
1328                         gistadjsubkey(r, itup, len, &v, giststate);
1329
1330                 pfree(v.spl_idgrp);
1331                 pfree(v.spl_grpflag);
1332                 pfree(v.spl_ngrp);
1333         }
1334
1335         /* clean up the entry vector: its keys need to be deleted, too */
1336         for (i = 1; i <= *len; i++)
1337                 if (decompvec[i])
1338                         pfree(DatumGetPointer(((GISTENTRY *) VARDATA(entryvec))[i].key));
1339         pfree(storage);                         /* pfree(entryvec); */
1340         pfree(decompvec);
1341
1342         /* form left and right vector */
1343         lvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nleft);
1344         rvectup = (IndexTuple *) palloc(sizeof(IndexTuple) * v.spl_nright);
1345
1346         for (i = 0; i < v.spl_nleft; i++)
1347                 lvectup[i] = itup[v.spl_left[i] - 1];
1348
1349         for (i = 0; i < v.spl_nright; i++)
1350                 rvectup[i] = itup[v.spl_right[i] - 1];
1351
1352
1353         /* write on disk (may be need another split) */
1354         if (gistnospace(right, rvectup, v.spl_nright))
1355         {
1356                 nlen = v.spl_nright;
1357                 newtup = gistSplit(r, rightbuf, rvectup, &nlen, giststate,
1358                           (res && rvectup[nlen - 1] == itup[*len - 1]) ? res : NULL);
1359                 ReleaseBuffer(rightbuf);
1360                 for (j = 1; j < r->rd_att->natts; j++)
1361                         if ((!isAttByVal(giststate, j)) && !v.spl_risnull[j])
1362                                 pfree(DatumGetPointer(v.spl_rattr[j]));
1363         }
1364         else
1365         {
1366                 OffsetNumber l;
1367
1368                 l = gistwritebuffer(r, right, rvectup, v.spl_nright, FirstOffsetNumber, giststate);
1369                 WriteBuffer(rightbuf);
1370
1371                 if (res)
1372                         ItemPointerSet(&((*res)->pointerData), rbknum, l);
1373
1374                 nlen = 1;
1375                 newtup = (IndexTuple *) palloc(sizeof(IndexTuple) * 1);
1376                 newtup[0] = gistFormTuple(giststate, r, v.spl_rattr, v.spl_rattrsize, v.spl_risnull);
1377                 ItemPointerSet(&(newtup[0]->t_tid), rbknum, 1);
1378         }
1379
1380
1381         if (gistnospace(left, lvectup, v.spl_nleft))
1382         {
1383                 int                     llen = v.spl_nleft;
1384                 IndexTuple *lntup;
1385
1386                 lntup = gistSplit(r, leftbuf, lvectup, &llen, giststate,
1387                           (res && lvectup[llen - 1] == itup[*len - 1]) ? res : NULL);
1388                 ReleaseBuffer(leftbuf);
1389
1390                 for (j = 1; j < r->rd_att->natts; j++)
1391                         if ((!isAttByVal(giststate, j)) && !v.spl_lisnull[j])
1392                                 pfree(DatumGetPointer(v.spl_lattr[j]));
1393
1394                 newtup = gistjoinvector(newtup, &nlen, lntup, llen);
1395                 pfree(lntup);
1396         }
1397         else
1398         {
1399                 OffsetNumber l;
1400
1401                 l = gistwritebuffer(r, left, lvectup, v.spl_nleft, FirstOffsetNumber, giststate);
1402                 if (BufferGetBlockNumber(buffer) != GISTP_ROOT)
1403                         PageRestoreTempPage(left, p);
1404
1405                 WriteBuffer(leftbuf);
1406
1407                 if (res)
1408                         ItemPointerSet(&((*res)->pointerData), lbknum, l);
1409
1410                 nlen += 1;
1411                 newtup = (IndexTuple *) repalloc((void *) newtup, sizeof(IndexTuple) * nlen);
1412                 newtup[nlen - 1] = gistFormTuple(giststate, r, v.spl_lattr, v.spl_lattrsize, v.spl_lisnull);
1413                 ItemPointerSet(&(newtup[nlen - 1]->t_tid), lbknum, 1);
1414         }
1415
1416
1417         /* adjust active scans */
1418         gistadjscans(r, GISTOP_SPLIT, BufferGetBlockNumber(buffer), FirstOffsetNumber);
1419
1420         /* !!! pfree */
1421         pfree(rvectup);
1422         pfree(lvectup);
1423         pfree(v.spl_left);
1424         pfree(v.spl_right);
1425
1426         *len = nlen;
1427         return newtup;
1428 }
1429
1430 static void
1431 gistnewroot(GISTSTATE *giststate, Relation r, IndexTuple *itup, int len)
1432 {
1433         Buffer          b;
1434         Page            p;
1435
1436         b = ReadBuffer(r, GISTP_ROOT);
1437         GISTInitBuffer(b, 0);
1438         p = BufferGetPage(b);
1439
1440         gistwritebuffer(r, p, itup, len, FirstOffsetNumber, giststate);
1441         WriteBuffer(b);
1442 }
1443
1444 static void
1445 GISTInitBuffer(Buffer b, uint32 f)
1446 {
1447         GISTPageOpaque opaque;
1448         Page            page;
1449         Size            pageSize;
1450
1451         pageSize = BufferGetPageSize(b);
1452
1453         page = BufferGetPage(b);
1454
1455         PageInit(page, pageSize, sizeof(GISTPageOpaqueData));
1456
1457         opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1458         opaque->flags = f;
1459 }
1460
1461
1462 /*
1463 ** find entry with lowest penalty
1464 */
1465 static OffsetNumber
1466 gistchoose(Relation r, Page p, IndexTuple it,   /* it has compressed entry */
1467                    GISTSTATE *giststate)
1468 {
1469         OffsetNumber maxoff;
1470         OffsetNumber i;
1471         Datum           datum;
1472         float           usize;
1473         OffsetNumber which;
1474         float           sum_grow,
1475                                 which_grow[INDEX_MAX_KEYS];
1476         GISTENTRY       entry,
1477                                 identry[INDEX_MAX_KEYS];
1478         bool            IsNull,
1479                                 decompvec[INDEX_MAX_KEYS],
1480                                 isnull[INDEX_MAX_KEYS];
1481         int                     j;
1482
1483         maxoff = PageGetMaxOffsetNumber(p);
1484         *which_grow = -1.0;
1485         which = -1;
1486         sum_grow = 1;
1487         gistDeCompressAtt(giststate, r,
1488                                           it, (Page) NULL, (OffsetNumber) 0,
1489                                           identry, decompvec, isnull);
1490
1491         for (i = FirstOffsetNumber; i <= maxoff && sum_grow; i = OffsetNumberNext(i))
1492         {
1493                 IndexTuple      itup = (IndexTuple) PageGetItem(p, PageGetItemId(p, i));
1494
1495                 sum_grow = 0;
1496                 for (j = 0; j < r->rd_att->natts; j++)
1497                 {
1498                         datum = index_getattr(itup, j + 1, giststate->tupdesc, &IsNull);
1499                         gistdentryinit(giststate, j, &entry, datum, r, p, i, ATTSIZE(datum, giststate->tupdesc, j + 1, IsNull), FALSE, IsNull);
1500                         gistpenalty(giststate, j, &entry, IsNull, &identry[j], isnull[j], &usize);
1501
1502                         if ((!isAttByVal(giststate, j)) && entry.key != datum)
1503                                 pfree(DatumGetPointer(entry.key));
1504
1505                         if (which_grow[j] < 0 || usize < which_grow[j])
1506                         {
1507                                 which = i;
1508                                 which_grow[j] = usize;
1509                                 if (j < r->rd_att->natts - 1 && i == FirstOffsetNumber)
1510                                         which_grow[j + 1] = -1;
1511                                 sum_grow += which_grow[j];
1512                         }
1513                         else if (which_grow[j] == usize)
1514                                 sum_grow += usize;
1515                         else
1516                         {
1517                                 sum_grow = 1;
1518                                 break;
1519                         }
1520                 }
1521         }
1522
1523         gistFreeAtt(r, identry, decompvec);
1524         return which;
1525 }
1526
1527 void
1528 gistfreestack(GISTSTACK *s)
1529 {
1530         GISTSTACK  *p;
1531
1532         while (s != (GISTSTACK *) NULL)
1533         {
1534                 p = s->gs_parent;
1535                 pfree(s);
1536                 s = p;
1537         }
1538 }
1539
1540
1541 /*
1542  * Retail deletion of a single tuple.
1543  *
1544  * NB: this is no longer called externally, but is still needed by
1545  * gistlayerinsert().  That dependency will have to be fixed if GIST
1546  * is ever going to allow concurrent insertions.
1547  */
1548 static void
1549 gistdelete(Relation r, ItemPointer tid)
1550 {
1551         BlockNumber blkno;
1552         OffsetNumber offnum;
1553         Buffer          buf;
1554         Page            page;
1555
1556         /*
1557          * Since GIST is not marked "amconcurrent" in pg_am, caller should
1558          * have acquired exclusive lock on index relation.      We need no locking
1559          * here.
1560          */
1561
1562         blkno = ItemPointerGetBlockNumber(tid);
1563         offnum = ItemPointerGetOffsetNumber(tid);
1564
1565         /* adjust any scans that will be affected by this deletion */
1566         /* NB: this works only for scans in *this* backend! */
1567         gistadjscans(r, GISTOP_DEL, blkno, offnum);
1568
1569         /* delete the index tuple */
1570         buf = ReadBuffer(r, blkno);
1571         page = BufferGetPage(buf);
1572
1573         PageIndexTupleDelete(page, offnum);
1574
1575         WriteBuffer(buf);
1576 }
1577
1578 /*
1579  * Bulk deletion of all index entries pointing to a set of heap tuples.
1580  * The set of target tuples is specified via a callback routine that tells
1581  * whether any given heap tuple (identified by ItemPointer) is being deleted.
1582  *
1583  * Result: a palloc'd struct containing statistical info for VACUUM displays.
1584  */
1585 Datum
1586 gistbulkdelete(PG_FUNCTION_ARGS)
1587 {
1588         Relation        rel = (Relation) PG_GETARG_POINTER(0);
1589         IndexBulkDeleteCallback callback = (IndexBulkDeleteCallback) PG_GETARG_POINTER(1);
1590         void       *callback_state = (void *) PG_GETARG_POINTER(2);
1591         IndexBulkDeleteResult *result;
1592         BlockNumber num_pages;
1593         double          tuples_removed;
1594         double          num_index_tuples;
1595         RetrieveIndexResult res;
1596         IndexScanDesc iscan;
1597
1598         tuples_removed = 0;
1599         num_index_tuples = 0;
1600
1601         /*
1602          * Since GIST is not marked "amconcurrent" in pg_am, caller should
1603          * have acquired exclusive lock on index relation.      We need no locking
1604          * here.
1605          */
1606
1607         /*
1608          * XXX generic implementation --- should be improved!
1609          */
1610
1611         /* walk through the entire index */
1612         iscan = index_beginscan(rel, false, 0, (ScanKey) NULL);
1613
1614         while ((res = index_getnext(iscan, ForwardScanDirection))
1615                    != (RetrieveIndexResult) NULL)
1616         {
1617                 ItemPointer heapptr = &res->heap_iptr;
1618
1619                 if (callback(heapptr, callback_state))
1620                 {
1621                         ItemPointer indexptr = &res->index_iptr;
1622                         BlockNumber blkno;
1623                         OffsetNumber offnum;
1624                         Buffer          buf;
1625                         Page            page;
1626
1627                         blkno = ItemPointerGetBlockNumber(indexptr);
1628                         offnum = ItemPointerGetOffsetNumber(indexptr);
1629
1630                         /* adjust any scans that will be affected by this deletion */
1631                         gistadjscans(rel, GISTOP_DEL, blkno, offnum);
1632
1633                         /* delete the index tuple */
1634                         buf = ReadBuffer(rel, blkno);
1635                         page = BufferGetPage(buf);
1636
1637                         PageIndexTupleDelete(page, offnum);
1638
1639                         WriteBuffer(buf);
1640
1641                         tuples_removed += 1;
1642                 }
1643                 else
1644                         num_index_tuples += 1;
1645
1646                 pfree(res);
1647         }
1648
1649         index_endscan(iscan);
1650
1651         /* return statistics */
1652         num_pages = RelationGetNumberOfBlocks(rel);
1653
1654         result = (IndexBulkDeleteResult *) palloc(sizeof(IndexBulkDeleteResult));
1655         result->num_pages = num_pages;
1656         result->tuples_removed = tuples_removed;
1657         result->num_index_tuples = num_index_tuples;
1658
1659         PG_RETURN_POINTER(result);
1660 }
1661
1662
1663 void
1664 initGISTstate(GISTSTATE *giststate, Relation index)
1665 {
1666         int                     i;
1667
1668         if (index->rd_att->natts > INDEX_MAX_KEYS)
1669                 elog(ERROR, "initGISTstate: numberOfAttributes %d > %d",
1670                          index->rd_att->natts, INDEX_MAX_KEYS);
1671
1672         giststate->tupdesc = index->rd_att;
1673
1674         for (i = 0; i < index->rd_att->natts; i++)
1675         {
1676                 fmgr_info_copy(&(giststate->consistentFn[i]),
1677                                    index_getprocinfo(index, i + 1, GIST_CONSISTENT_PROC),
1678                                            CurrentMemoryContext);
1679                 fmgr_info_copy(&(giststate->unionFn[i]),
1680                                            index_getprocinfo(index, i + 1, GIST_UNION_PROC),
1681                                            CurrentMemoryContext);
1682                 fmgr_info_copy(&(giststate->compressFn[i]),
1683                                          index_getprocinfo(index, i + 1, GIST_COMPRESS_PROC),
1684                                            CurrentMemoryContext);
1685                 fmgr_info_copy(&(giststate->decompressFn[i]),
1686                                    index_getprocinfo(index, i + 1, GIST_DECOMPRESS_PROC),
1687                                            CurrentMemoryContext);
1688                 fmgr_info_copy(&(giststate->penaltyFn[i]),
1689                                            index_getprocinfo(index, i + 1, GIST_PENALTY_PROC),
1690                                            CurrentMemoryContext);
1691                 fmgr_info_copy(&(giststate->picksplitFn[i]),
1692                                         index_getprocinfo(index, i + 1, GIST_PICKSPLIT_PROC),
1693                                            CurrentMemoryContext);
1694                 fmgr_info_copy(&(giststate->equalFn[i]),
1695                                            index_getprocinfo(index, i + 1, GIST_EQUAL_PROC),
1696                                            CurrentMemoryContext);
1697         }
1698 }
1699
1700 void
1701 freeGISTstate(GISTSTATE *giststate)
1702 {
1703         /* no work */
1704 }
1705
1706 #ifdef GIST_PAGEADDITEM
1707 /*
1708 ** Given an IndexTuple to be inserted on a page, this routine replaces
1709 ** the key with another key, which may involve generating a new IndexTuple
1710 ** if the sizes don't match or if the null status changes.
1711 **
1712 ** XXX this only works for a single-column index tuple!
1713 */
1714 static IndexTuple
1715 gist_tuple_replacekey(Relation r, GISTENTRY entry, IndexTuple t)
1716 {
1717         bool            IsNull;
1718         Datum           datum = index_getattr(t, 1, r->rd_att, &IsNull);
1719
1720         /*
1721          * If new entry fits in index tuple, copy it in.  To avoid worrying
1722          * about null-value bitmask, pass it off to the general
1723          * index_formtuple routine if either the previous or new value is
1724          * NULL.
1725          */
1726         if (!IsNull && DatumGetPointer(entry.key) != NULL &&
1727                 (Size) entry.bytes <= ATTSIZE(datum, r, 1, IsNull))
1728         {
1729                 memcpy(DatumGetPointer(datum),
1730                            DatumGetPointer(entry.key),
1731                            entry.bytes);
1732                 /* clear out old size */
1733                 t->t_info &= ~INDEX_SIZE_MASK;
1734                 /* or in new size */
1735                 t->t_info |= MAXALIGN(entry.bytes + sizeof(IndexTupleData));
1736
1737                 return t;
1738         }
1739         else
1740         {
1741                 /* generate a new index tuple for the compressed entry */
1742                 TupleDesc       tupDesc = r->rd_att;
1743                 IndexTuple      newtup;
1744                 char            isnull;
1745
1746                 isnull = DatumGetPointer(entry.key) != NULL ? ' ' : 'n';
1747                 newtup = (IndexTuple) index_formtuple(tupDesc,
1748                                                                                           &(entry.key),
1749                                                                                           &isnull);
1750                 newtup->t_tid = t->t_tid;
1751                 return newtup;
1752         }
1753 }
1754 #endif
1755
1756 /*
1757 ** initialize a GiST entry with a decompressed version of key
1758 */
1759 void
1760 gistdentryinit(GISTSTATE *giststate, int nkey, GISTENTRY *e,
1761                            Datum k, Relation r, Page pg, OffsetNumber o,
1762                            int b, bool l, bool isNull)
1763 {
1764         if (b && !isNull)
1765         {
1766                 GISTENTRY  *dep;
1767
1768                 gistentryinit(*e, k, r, pg, o, b, l);
1769                 dep = (GISTENTRY *)
1770                         DatumGetPointer(FunctionCall1(&giststate->decompressFn[nkey],
1771                                                                                   PointerGetDatum(e)));
1772                 /* decompressFn may just return the given pointer */
1773                 if (dep != e)
1774                 {
1775                         gistentryinit(*e, dep->key, dep->rel, dep->page, dep->offset,
1776                                                   dep->bytes, dep->leafkey);
1777                         pfree(dep);
1778                 }
1779         }
1780         else
1781                 gistentryinit(*e, (Datum) 0, r, pg, o, 0, l);
1782 }
1783
1784
1785 /*
1786 ** initialize a GiST entry with a compressed version of key
1787 */
1788 static void
1789 gistcentryinit(GISTSTATE *giststate, int nkey,
1790                            GISTENTRY *e, Datum k, Relation r,
1791                            Page pg, OffsetNumber o, int b, bool l, bool isNull)
1792 {
1793         if (!isNull)
1794         {
1795                 GISTENTRY  *cep;
1796
1797                 gistentryinit(*e, k, r, pg, o, b, l);
1798                 cep = (GISTENTRY *)
1799                         DatumGetPointer(FunctionCall1(&giststate->compressFn[nkey],
1800                                                                                   PointerGetDatum(e)));
1801                 /* compressFn may just return the given pointer */
1802                 if (cep != e)
1803                 {
1804                         gistentryinit(*e, cep->key, cep->rel, cep->page, cep->offset,
1805                                                   cep->bytes, cep->leafkey);
1806                         pfree(cep);
1807                 }
1808         }
1809         else
1810                 gistentryinit(*e, (Datum) 0, r, pg, o, 0, l);
1811 }
1812
1813 static IndexTuple
1814 gistFormTuple(GISTSTATE *giststate, Relation r,
1815                           Datum attdata[], int datumsize[], bool isnull[])
1816 {
1817         IndexTuple      tup;
1818         char            isnullchar[INDEX_MAX_KEYS];
1819         bool            whatfree[INDEX_MAX_KEYS];
1820         GISTENTRY       centry[INDEX_MAX_KEYS];
1821         Datum           compatt[INDEX_MAX_KEYS];
1822         int                     j;
1823
1824         for (j = 0; j < r->rd_att->natts; j++)
1825         {
1826                 if (isnull[j])
1827                 {
1828                         isnullchar[j] = 'n';
1829                         compatt[j] = (Datum) 0;
1830                         whatfree[j] = FALSE;
1831                 }
1832                 else
1833                 {
1834                         gistcentryinit(giststate, j, &centry[j], attdata[j],
1835                                            (Relation) NULL, (Page) NULL, (OffsetNumber) NULL,
1836                                                    datumsize[j], FALSE, FALSE);
1837                         isnullchar[j] = ' ';
1838                         compatt[j] = centry[j].key;
1839                         if (!isAttByVal(giststate, j))
1840                         {
1841                                 whatfree[j] = TRUE;
1842                                 if (centry[j].key != attdata[j])
1843                                         pfree(DatumGetPointer(attdata[j]));
1844                         }
1845                         else
1846                                 whatfree[j] = FALSE;
1847                 }
1848         }
1849
1850         tup = (IndexTuple) index_formtuple(giststate->tupdesc, compatt, isnullchar);
1851         for (j = 0; j < r->rd_att->natts; j++)
1852                 if (whatfree[j])
1853                         pfree(DatumGetPointer(compatt[j]));
1854
1855         return tup;
1856 }
1857
1858 static void
1859 gistDeCompressAtt(GISTSTATE *giststate, Relation r, IndexTuple tuple, Page p,
1860         OffsetNumber o, GISTENTRY attdata[], bool decompvec[], bool isnull[])
1861 {
1862         int                     i;
1863         Datum           datum;
1864
1865         for (i = 0; i < r->rd_att->natts; i++)
1866         {
1867                 datum = index_getattr(tuple, i + 1, giststate->tupdesc, &isnull[i]);
1868                 gistdentryinit(giststate, i, &attdata[i],
1869                                            datum, r, p, o,
1870                                            ATTSIZE(datum, giststate->tupdesc, i + 1, isnull[i]), FALSE, isnull[i]);
1871                 if (isAttByVal(giststate, i))
1872                         decompvec[i] = FALSE;
1873                 else
1874                 {
1875                         if (attdata[i].key == datum || isnull[i])
1876                                 decompvec[i] = FALSE;
1877                         else
1878                                 decompvec[i] = TRUE;
1879                 }
1880         }
1881 }
1882
1883 static void
1884 gistFreeAtt(Relation r, GISTENTRY attdata[], bool decompvec[])
1885 {
1886         int                     i;
1887
1888         for (i = 0; i < r->rd_att->natts; i++)
1889                 if (decompvec[i])
1890                         pfree(DatumGetPointer(attdata[i].key));
1891 }
1892
1893 static void
1894 gistpenalty(GISTSTATE *giststate, int attno,
1895                         GISTENTRY *key1, bool isNull1,
1896                         GISTENTRY *key2, bool isNull2, float *penalty)
1897 {
1898         if (giststate->penaltyFn[attno].fn_strict && (isNull1 || isNull2))
1899                 *penalty = 0.0;
1900         else
1901                 FunctionCall3(&giststate->penaltyFn[attno],
1902                                           PointerGetDatum(key1),
1903                                           PointerGetDatum(key2),
1904                                           PointerGetDatum(penalty));
1905 }
1906
1907 #ifdef GISTDEBUG
1908 static void
1909 gist_dumptree(Relation r, int level, BlockNumber blk, OffsetNumber coff)
1910 {
1911         Buffer          buffer;
1912         Page            page;
1913         GISTPageOpaque opaque;
1914         IndexTuple      which;
1915         ItemId          iid;
1916         OffsetNumber i,
1917                                 maxoff;
1918         BlockNumber cblk;
1919         char       *pred;
1920
1921         pred = (char *) palloc(sizeof(char) * level + 1);
1922         MemSet(pred, '\t', level);
1923         pred[level] = '\0';
1924
1925         buffer = ReadBuffer(r, blk);
1926         page = (Page) BufferGetPage(buffer);
1927         opaque = (GISTPageOpaque) PageGetSpecialPointer(page);
1928
1929         maxoff = PageGetMaxOffsetNumber(page);
1930
1931         elog(NOTICE, "%sPage: %d %s blk: %d maxoff: %d free: %d", pred,
1932                  coff, (opaque->flags & F_LEAF) ? "LEAF" : "INTE", (int) blk,
1933                  (int) maxoff, PageGetFreeSpace(page));
1934
1935         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1936         {
1937                 iid = PageGetItemId(page, i);
1938                 which = (IndexTuple) PageGetItem(page, iid);
1939                 cblk = ItemPointerGetBlockNumber(&(which->t_tid));
1940 #ifdef PRINTTUPLE
1941                 elog(NOTICE, "%s  Tuple. blk: %d size: %d", pred, (int) cblk,
1942                          IndexTupleSize(which));
1943 #endif
1944
1945                 if (!(opaque->flags & F_LEAF))
1946                         gist_dumptree(r, level + 1, cblk, i);
1947         }
1948         ReleaseBuffer(buffer);
1949         pfree(pred);
1950 }
1951 #endif   /* defined GISTDEBUG */
1952
1953 void
1954 gist_redo(XLogRecPtr lsn, XLogRecord *record)
1955 {
1956         elog(STOP, "gist_redo: unimplemented");
1957 }
1958
1959 void
1960 gist_undo(XLogRecPtr lsn, XLogRecord *record)
1961 {
1962         elog(STOP, "gist_undo: unimplemented");
1963 }
1964
1965 void
1966 gist_desc(char *buf, uint8 xl_info, char *rec)
1967 {
1968 }