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