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

   1 /*-------------------------------------------------------------------------
   2  *
   3  * ginentrypage.c
   4  *        routines for handling GIN entry tree pages.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *                      src/backend/access/gin/ginentrypage.c
  12  *-------------------------------------------------------------------------
  13  */
  14
  15 #include "postgres.h"
  16
  17 #include "access/gin_private.h"
  18 #include "access/xloginsert.h"
  19 #include "miscadmin.h"
  20 #include "utils/rel.h"
  21
  22 static void entrySplitPage(GinBtree btree, Buffer origbuf,
  23                            GinBtreeStack *stack,
  24                            void *insertPayload,
  25                            BlockNumber updateblkno, XLogRecData **prdata,
  26                            Page *newlpage, Page *newrpage);
  27
  28 /*
  29  * Form a tuple for entry tree.
  30  *
  31  * If the tuple would be too big to be stored, function throws a suitable
  32  * error if errorTooBig is TRUE, or returns NULL if errorTooBig is FALSE.
  33  *
  34  * See src/backend/access/gin/README for a description of the index tuple
  35  * format that is being built here.  We build on the assumption that we
  36  * are making a leaf-level key entry containing a posting list of nipd items.
  37  * If the caller is actually trying to make a posting-tree entry, non-leaf
  38  * entry, or pending-list entry, it should pass dataSize = 0 and then overwrite
  39  * the t_tid fields as necessary.  In any case, 'data' can be NULL to skip
  40  * filling in the posting list; the caller is responsible for filling it
  41  * afterwards if data = NULL and nipd > 0.
  42  */
  43 IndexTuple
  44 GinFormTuple(GinState *ginstate,
  45                          OffsetNumber attnum, Datum key, GinNullCategory category,
  46                          Pointer data, Size dataSize, int nipd,
  47                          bool errorTooBig)
  48 {
  49         Datum           datums[2];
  50         bool            isnull[2];
  51         IndexTuple      itup;
  52         uint32          newsize;
  53
  54         /* Build the basic tuple: optional column number, plus key datum */
  55         if (ginstate->oneCol)
  56         {
  57                 datums[0] = key;
  58                 isnull[0] = (category != GIN_CAT_NORM_KEY);
  59         }
  60         else
  61         {
  62                 datums[0] = UInt16GetDatum(attnum);
  63                 isnull[0] = false;
  64                 datums[1] = key;
  65                 isnull[1] = (category != GIN_CAT_NORM_KEY);
  66         }
  67
  68         itup = index_form_tuple(ginstate->tupdesc[attnum - 1], datums, isnull);
  69
  70         /*
  71          * Determine and store offset to the posting list, making sure there is
  72          * room for the category byte if needed.
  73          *
  74          * Note: because index_form_tuple MAXALIGNs the tuple size, there may well
  75          * be some wasted pad space.  Is it worth recomputing the data length to
  76          * prevent that?  That would also allow us to Assert that the real data
  77          * doesn't overlap the GinNullCategory byte, which this code currently
  78          * takes on faith.
  79          */
  80         newsize = IndexTupleSize(itup);
  81
  82         if (IndexTupleHasNulls(itup))
  83         {
  84                 uint32          minsize;
  85
  86                 Assert(category != GIN_CAT_NORM_KEY);
  87                 minsize = GinCategoryOffset(itup, ginstate) + sizeof(GinNullCategory);
  88                 newsize = Max(newsize, minsize);
  89         }
  90
  91         newsize = SHORTALIGN(newsize);
  92
  93         GinSetPostingOffset(itup, newsize);
  94         GinSetNPosting(itup, nipd);
  95
  96         /*
  97          * Add space needed for posting list, if any.  Then check that the tuple
  98          * won't be too big to store.
  99          */
 100         newsize += dataSize;
 101
 102         newsize = MAXALIGN(newsize);
 103
 104         if (newsize > GinMaxItemSize)
 105         {
 106                 if (errorTooBig)
 107                         ereport(ERROR,
 108                                         (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
 109                         errmsg("index row size %zu exceeds maximum %zu for index \"%s\"",
 110                                    (Size) newsize, (Size) GinMaxItemSize,
 111                                    RelationGetRelationName(ginstate->index))));
 112                 pfree(itup);
 113                 return NULL;
 114         }
 115
 116         /*
 117          * Resize tuple if needed
 118          */
 119         if (newsize != IndexTupleSize(itup))
 120         {
 121                 itup = repalloc(itup, newsize);
 122
 123                 /*
 124                  * PostgreSQL 9.3 and earlier did not clear this new space, so we
 125                  * might find uninitialized padding when reading tuples from disk.
 126                  */
 127                 memset((char *) itup + IndexTupleSize(itup),
 128                            0, newsize - IndexTupleSize(itup));
 129                 /* set new size in tuple header */
 130                 itup->t_info &= ~INDEX_SIZE_MASK;
 131                 itup->t_info |= newsize;
 132         }
 133
 134         /*
 135          * Copy in the posting list, if provided
 136          */
 137         if (data)
 138         {
 139                 char       *ptr = GinGetPosting(itup);
 140
 141                 memcpy(ptr, data, dataSize);
 142         }
 143
 144         /*
 145          * Insert category byte, if needed
 146          */
 147         if (category != GIN_CAT_NORM_KEY)
 148         {
 149                 Assert(IndexTupleHasNulls(itup));
 150                 GinSetNullCategory(itup, ginstate, category);
 151         }
 152         return itup;
 153 }
 154
 155 /*
 156  * Read item pointers from leaf entry tuple.
 157  *
 158  * Returns a palloc'd array of ItemPointers. The number of items is returned
 159  * in *nitems.
 160  */
 161 ItemPointer
 162 ginReadTuple(GinState *ginstate, OffsetNumber attnum, IndexTuple itup,
 163                          int *nitems)
 164 {
 165         Pointer         ptr = GinGetPosting(itup);
 166         int                     nipd = GinGetNPosting(itup);
 167         ItemPointer ipd;
 168         int                     ndecoded;
 169
 170         if (GinItupIsCompressed(itup))
 171         {
 172                 if (nipd > 0)
 173                 {
 174                         ipd = ginPostingListDecode((GinPostingList *) ptr, &ndecoded);
 175                         if (nipd != ndecoded)
 176                                 elog(ERROR, "number of items mismatch in GIN entry tuple, %d in tuple header, %d decoded",
 177                                          nipd, ndecoded);
 178                 }
 179                 else
 180                 {
 181                         ipd = palloc(0);
 182                 }
 183         }
 184         else
 185         {
 186                 ipd = (ItemPointer) palloc(sizeof(ItemPointerData) * nipd);
 187                 memcpy(ipd, ptr, sizeof(ItemPointerData) * nipd);
 188         }
 189         *nitems = nipd;
 190         return ipd;
 191 }
 192
 193 /*
 194  * Form a non-leaf entry tuple by copying the key data from the given tuple,
 195  * which can be either a leaf or non-leaf entry tuple.
 196  *
 197  * Any posting list in the source tuple is not copied.  The specified child
 198  * block number is inserted into t_tid.
 199  */
 200 static IndexTuple
 201 GinFormInteriorTuple(IndexTuple itup, Page page, BlockNumber childblk)
 202 {
 203         IndexTuple      nitup;
 204
 205         if (GinPageIsLeaf(page) && !GinIsPostingTree(itup))
 206         {
 207                 /* Tuple contains a posting list, just copy stuff before that */
 208                 uint32          origsize = GinGetPostingOffset(itup);
 209
 210                 origsize = MAXALIGN(origsize);
 211                 nitup = (IndexTuple) palloc(origsize);
 212                 memcpy(nitup, itup, origsize);
 213                 /* ... be sure to fix the size header field ... */
 214                 nitup->t_info &= ~INDEX_SIZE_MASK;
 215                 nitup->t_info |= origsize;
 216         }
 217         else
 218         {
 219                 /* Copy the tuple as-is */
 220                 nitup = (IndexTuple) palloc(IndexTupleSize(itup));
 221                 memcpy(nitup, itup, IndexTupleSize(itup));
 222         }
 223
 224         /* Now insert the correct downlink */
 225         GinSetDownlink(nitup, childblk);
 226
 227         return nitup;
 228 }
 229
 230 /*
 231  * Entry tree is a "static", ie tuple never deletes from it,
 232  * so we don't use right bound, we use rightmost key instead.
 233  */
 234 static IndexTuple
 235 getRightMostTuple(Page page)
 236 {
 237         OffsetNumber maxoff = PageGetMaxOffsetNumber(page);
 238
 239         return (IndexTuple) PageGetItem(page, PageGetItemId(page, maxoff));
 240 }
 241
 242 static bool
 243 entryIsMoveRight(GinBtree btree, Page page)
 244 {
 245         IndexTuple      itup;
 246         OffsetNumber attnum;
 247         Datum           key;
 248         GinNullCategory category;
 249
 250         if (GinPageRightMost(page))
 251                 return FALSE;
 252
 253         itup = getRightMostTuple(page);
 254         attnum = gintuple_get_attrnum(btree->ginstate, itup);
 255         key = gintuple_get_key(btree->ginstate, itup, &category);
 256
 257         if (ginCompareAttEntries(btree->ginstate,
 258                                    btree->entryAttnum, btree->entryKey, btree->entryCategory,
 259                                                          attnum, key, category) > 0)
 260                 return TRUE;
 261
 262         return FALSE;
 263 }
 264
 265 /*
 266  * Find correct tuple in non-leaf page. It supposed that
 267  * page correctly chosen and searching value SHOULD be on page
 268  */
 269 static BlockNumber
 270 entryLocateEntry(GinBtree btree, GinBtreeStack *stack)
 271 {
 272         OffsetNumber low,
 273                                 high,
 274                                 maxoff;
 275         IndexTuple      itup = NULL;
 276         int                     result;
 277         Page            page = BufferGetPage(stack->buffer);
 278
 279         Assert(!GinPageIsLeaf(page));
 280         Assert(!GinPageIsData(page));
 281
 282         if (btree->fullScan)
 283         {
 284                 stack->off = FirstOffsetNumber;
 285                 stack->predictNumber *= PageGetMaxOffsetNumber(page);
 286                 return btree->getLeftMostChild(btree, page);
 287         }
 288
 289         low = FirstOffsetNumber;
 290         maxoff = high = PageGetMaxOffsetNumber(page);
 291         Assert(high >= low);
 292
 293         high++;
 294
 295         while (high > low)
 296         {
 297                 OffsetNumber mid = low + ((high - low) / 2);
 298
 299                 if (mid == maxoff && GinPageRightMost(page))
 300                 {
 301                         /* Right infinity */
 302                         result = -1;
 303                 }
 304                 else
 305                 {
 306                         OffsetNumber attnum;
 307                         Datum           key;
 308                         GinNullCategory category;
 309
 310                         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, mid));
 311                         attnum = gintuple_get_attrnum(btree->ginstate, itup);
 312                         key = gintuple_get_key(btree->ginstate, itup, &category);
 313                         result = ginCompareAttEntries(btree->ginstate,
 314                                                                                   btree->entryAttnum,
 315                                                                                   btree->entryKey,
 316                                                                                   btree->entryCategory,
 317                                                                                   attnum, key, category);
 318                 }
 319
 320                 if (result == 0)
 321                 {
 322                         stack->off = mid;
 323                         Assert(GinGetDownlink(itup) != GIN_ROOT_BLKNO);
 324                         return GinGetDownlink(itup);
 325                 }
 326                 else if (result > 0)
 327                         low = mid + 1;
 328                 else
 329                         high = mid;
 330         }
 331
 332         Assert(high >= FirstOffsetNumber && high <= maxoff);
 333
 334         stack->off = high;
 335         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, high));
 336         Assert(GinGetDownlink(itup) != GIN_ROOT_BLKNO);
 337         return GinGetDownlink(itup);
 338 }
 339
 340 /*
 341  * Searches correct position for value on leaf page.
 342  * Page should be correctly chosen.
 343  * Returns true if value found on page.
 344  */
 345 static bool
 346 entryLocateLeafEntry(GinBtree btree, GinBtreeStack *stack)
 347 {
 348         Page            page = BufferGetPage(stack->buffer);
 349         OffsetNumber low,
 350                                 high;
 351
 352         Assert(GinPageIsLeaf(page));
 353         Assert(!GinPageIsData(page));
 354
 355         if (btree->fullScan)
 356         {
 357                 stack->off = FirstOffsetNumber;
 358                 return TRUE;
 359         }
 360
 361         low = FirstOffsetNumber;
 362         high = PageGetMaxOffsetNumber(page);
 363
 364         if (high < low)
 365         {
 366                 stack->off = FirstOffsetNumber;
 367                 return false;
 368         }
 369
 370         high++;
 371
 372         while (high > low)
 373         {
 374                 OffsetNumber mid = low + ((high - low) / 2);
 375                 IndexTuple      itup;
 376                 OffsetNumber attnum;
 377                 Datum           key;
 378                 GinNullCategory category;
 379                 int                     result;
 380
 381                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, mid));
 382                 attnum = gintuple_get_attrnum(btree->ginstate, itup);
 383                 key = gintuple_get_key(btree->ginstate, itup, &category);
 384                 result = ginCompareAttEntries(btree->ginstate,
 385                                                                           btree->entryAttnum,
 386                                                                           btree->entryKey,
 387                                                                           btree->entryCategory,
 388                                                                           attnum, key, category);
 389                 if (result == 0)
 390                 {
 391                         stack->off = mid;
 392                         return true;
 393                 }
 394                 else if (result > 0)
 395                         low = mid + 1;
 396                 else
 397                         high = mid;
 398         }
 399
 400         stack->off = high;
 401         return false;
 402 }
 403
 404 static OffsetNumber
 405 entryFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
 406 {
 407         OffsetNumber i,
 408                                 maxoff = PageGetMaxOffsetNumber(page);
 409         IndexTuple      itup;
 410
 411         Assert(!GinPageIsLeaf(page));
 412         Assert(!GinPageIsData(page));
 413
 414         /* if page isn't changed, we returns storedOff */
 415         if (storedOff >= FirstOffsetNumber && storedOff <= maxoff)
 416         {
 417                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, storedOff));
 418                 if (GinGetDownlink(itup) == blkno)
 419                         return storedOff;
 420
 421                 /*
 422                  * we hope, that needed pointer goes to right. It's true if there
 423                  * wasn't a deletion
 424                  */
 425                 for (i = storedOff + 1; i <= maxoff; i++)
 426                 {
 427                         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
 428                         if (GinGetDownlink(itup) == blkno)
 429                                 return i;
 430                 }
 431                 maxoff = storedOff - 1;
 432         }
 433
 434         /* last chance */
 435         for (i = FirstOffsetNumber; i <= maxoff; i++)
 436         {
 437                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, i));
 438                 if (GinGetDownlink(itup) == blkno)
 439                         return i;
 440         }
 441
 442         return InvalidOffsetNumber;
 443 }
 444
 445 static BlockNumber
 446 entryGetLeftMostPage(GinBtree btree, Page page)
 447 {
 448         IndexTuple      itup;
 449
 450         Assert(!GinPageIsLeaf(page));
 451         Assert(!GinPageIsData(page));
 452         Assert(PageGetMaxOffsetNumber(page) >= FirstOffsetNumber);
 453
 454         itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, FirstOffsetNumber));
 455         return GinGetDownlink(itup);
 456 }
 457
 458 static bool
 459 entryIsEnoughSpace(GinBtree btree, Buffer buf, OffsetNumber off,
 460                                    GinBtreeEntryInsertData *insertData)
 461 {
 462         Size            releasedsz = 0;
 463         Size            addedsz;
 464         Page            page = BufferGetPage(buf);
 465
 466         Assert(insertData->entry);
 467         Assert(!GinPageIsData(page));
 468
 469         if (insertData->isDelete)
 470         {
 471                 IndexTuple      itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
 472
 473                 releasedsz = MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData);
 474         }
 475
 476         addedsz = MAXALIGN(IndexTupleSize(insertData->entry)) + sizeof(ItemIdData);
 477
 478         if (PageGetFreeSpace(page) + releasedsz >= addedsz)
 479                 return true;
 480
 481         return false;
 482 }
 483
 484 /*
 485  * Delete tuple on leaf page if tuples existed and we
 486  * should update it, update old child blkno to new right page
 487  * if child split occurred
 488  */
 489 static void
 490 entryPreparePage(GinBtree btree, Page page, OffsetNumber off,
 491                                  GinBtreeEntryInsertData *insertData, BlockNumber updateblkno)
 492 {
 493         Assert(insertData->entry);
 494         Assert(!GinPageIsData(page));
 495
 496         if (insertData->isDelete)
 497         {
 498                 Assert(GinPageIsLeaf(page));
 499                 PageIndexTupleDelete(page, off);
 500         }
 501
 502         if (!GinPageIsLeaf(page) && updateblkno != InvalidBlockNumber)
 503         {
 504                 IndexTuple      itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, off));
 505
 506                 GinSetDownlink(itup, updateblkno);
 507         }
 508 }
 509
 510 /*
 511  * Place tuple on page and fills WAL record
 512  *
 513  * If the tuple doesn't fit, returns false without modifying the page.
 514  *
 515  * On insertion to an internal node, in addition to inserting the given item,
 516  * the downlink of the existing item at 'off' is updated to point to
 517  * 'updateblkno'.
 518  */
 519 static GinPlaceToPageRC
 520 entryPlaceToPage(GinBtree btree, Buffer buf, GinBtreeStack *stack,
 521                                  void *insertPayload, BlockNumber updateblkno,
 522                                  XLogRecData **prdata, Page *newlpage, Page *newrpage)
 523 {
 524         GinBtreeEntryInsertData *insertData = insertPayload;
 525         Page            page = BufferGetPage(buf);
 526         OffsetNumber off = stack->off;
 527         OffsetNumber placed;
 528         int                     cnt = 0;
 529
 530         /* these must be static so they can be returned to caller */
 531         static XLogRecData rdata[3];
 532         static ginxlogInsertEntry data;
 533
 534         /* quick exit if it doesn't fit */
 535         if (!entryIsEnoughSpace(btree, buf, off, insertData))
 536         {
 537                 entrySplitPage(btree, buf, stack, insertPayload, updateblkno,
 538                                            prdata, newlpage, newrpage);
 539                 return SPLIT;
 540         }
 541
 542         START_CRIT_SECTION();
 543
 544         *prdata = rdata;
 545         entryPreparePage(btree, page, off, insertData, updateblkno);
 546
 547         placed = PageAddItem(page,
 548                                                  (Item) insertData->entry,
 549                                                  IndexTupleSize(insertData->entry),
 550                                                  off, false, false);
 551         if (placed != off)
 552                 elog(ERROR, "failed to add item to index page in \"%s\"",
 553                          RelationGetRelationName(btree->index));
 554
 555         data.isDelete = insertData->isDelete;
 556         data.offset = off;
 557
 558         rdata[cnt].buffer = buf;
 559         rdata[cnt].buffer_std = true;
 560         rdata[cnt].data = (char *) &data;
 561         rdata[cnt].len = offsetof(ginxlogInsertEntry, tuple);
 562         rdata[cnt].next = &rdata[cnt + 1];
 563         cnt++;
 564
 565         rdata[cnt].buffer = buf;
 566         rdata[cnt].buffer_std = true;
 567         rdata[cnt].data = (char *) insertData->entry;
 568         rdata[cnt].len = IndexTupleSize(insertData->entry);
 569         rdata[cnt].next = NULL;
 570
 571         return INSERTED;
 572 }
 573
 574 /*
 575  * Place tuple and split page, original buffer(lbuf) leaves untouched,
 576  * returns shadow pages filled with new data.
 577  * Tuples are distributed between pages by equal size on its, not
 578  * an equal number!
 579  */
 580 static void
 581 entrySplitPage(GinBtree btree, Buffer origbuf,
 582                            GinBtreeStack *stack,
 583                            void *insertPayload,
 584                            BlockNumber updateblkno, XLogRecData **prdata,
 585                            Page *newlpage, Page *newrpage)
 586 {
 587         GinBtreeEntryInsertData *insertData = insertPayload;
 588         OffsetNumber off = stack->off;
 589         OffsetNumber i,
 590                                 maxoff,
 591                                 separator = InvalidOffsetNumber;
 592         Size            totalsize = 0;
 593         Size            tupstoresize;
 594         Size            lsize = 0,
 595                                 size;
 596         char       *ptr;
 597         IndexTuple      itup;
 598         Page            page;
 599         Page            lpage = PageGetTempPageCopy(BufferGetPage(origbuf));
 600         Page            rpage = PageGetTempPageCopy(BufferGetPage(origbuf));
 601         Size            pageSize = PageGetPageSize(lpage);
 602
 603         /* these must be static so they can be returned to caller */
 604         static XLogRecData rdata[2];
 605         static ginxlogSplitEntry data;
 606         static char tupstore[2 * BLCKSZ];
 607
 608         *prdata = rdata;
 609         entryPreparePage(btree, lpage, off, insertData, updateblkno);
 610
 611         /*
 612          * First, append all the existing tuples and the new tuple we're inserting
 613          * one after another in a temporary workspace.
 614          */
 615         maxoff = PageGetMaxOffsetNumber(lpage);
 616         ptr = tupstore;
 617         for (i = FirstOffsetNumber; i <= maxoff; i++)
 618         {
 619                 if (i == off)
 620                 {
 621                         size = MAXALIGN(IndexTupleSize(insertData->entry));
 622                         memcpy(ptr, insertData->entry, size);
 623                         ptr += size;
 624                         totalsize += size + sizeof(ItemIdData);
 625                 }
 626
 627                 itup = (IndexTuple) PageGetItem(lpage, PageGetItemId(lpage, i));
 628                 size = MAXALIGN(IndexTupleSize(itup));
 629                 memcpy(ptr, itup, size);
 630                 ptr += size;
 631                 totalsize += size + sizeof(ItemIdData);
 632         }
 633
 634         if (off == maxoff + 1)
 635         {
 636                 size = MAXALIGN(IndexTupleSize(insertData->entry));
 637                 memcpy(ptr, insertData->entry, size);
 638                 ptr += size;
 639                 totalsize += size + sizeof(ItemIdData);
 640         }
 641         tupstoresize = ptr - tupstore;
 642
 643         /*
 644          * Initialize the left and right pages, and copy all the tuples back to
 645          * them.
 646          */
 647         GinInitPage(rpage, GinPageGetOpaque(lpage)->flags, pageSize);
 648         GinInitPage(lpage, GinPageGetOpaque(rpage)->flags, pageSize);
 649
 650         ptr = tupstore;
 651         maxoff++;
 652         lsize = 0;
 653
 654         page = lpage;
 655         for (i = FirstOffsetNumber; i <= maxoff; i++)
 656         {
 657                 itup = (IndexTuple) ptr;
 658
 659                 if (lsize > totalsize / 2)
 660                 {
 661                         if (separator == InvalidOffsetNumber)
 662                                 separator = i - 1;
 663                         page = rpage;
 664                 }
 665                 else
 666                 {
 667                         lsize += MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData);
 668                 }
 669
 670                 if (PageAddItem(page, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
 671                         elog(ERROR, "failed to add item to index page in \"%s\"",
 672                                  RelationGetRelationName(btree->index));
 673                 ptr += MAXALIGN(IndexTupleSize(itup));
 674         }
 675
 676         data.separator = separator;
 677         data.nitem = maxoff;
 678
 679         rdata[0].buffer = InvalidBuffer;
 680         rdata[0].data = (char *) &data;
 681         rdata[0].len = sizeof(ginxlogSplitEntry);
 682         rdata[0].next = &rdata[1];
 683
 684         rdata[1].buffer = InvalidBuffer;
 685         rdata[1].data = tupstore;
 686         rdata[1].len = tupstoresize;
 687         rdata[1].next = NULL;
 688
 689         *newlpage = lpage;
 690         *newrpage = rpage;
 691 }
 692
 693 /*
 694  * Construct insertion payload for inserting the downlink for given buffer.
 695  */
 696 static void *
 697 entryPrepareDownlink(GinBtree btree, Buffer lbuf)
 698 {
 699         GinBtreeEntryInsertData *insertData;
 700         Page            lpage = BufferGetPage(lbuf);
 701         BlockNumber lblkno = BufferGetBlockNumber(lbuf);
 702         IndexTuple      itup;
 703
 704         itup = getRightMostTuple(lpage);
 705
 706         insertData = palloc(sizeof(GinBtreeEntryInsertData));
 707         insertData->entry = GinFormInteriorTuple(itup, lpage, lblkno);
 708         insertData->isDelete = false;
 709
 710         return insertData;
 711 }
 712
 713 /*
 714  * Fills new root by rightest values from child.
 715  * Also called from ginxlog, should not use btree
 716  */
 717 void
 718 ginEntryFillRoot(GinBtree btree, Page root,
 719                                  BlockNumber lblkno, Page lpage,
 720                                  BlockNumber rblkno, Page rpage)
 721 {
 722         IndexTuple      itup;
 723
 724         itup = GinFormInteriorTuple(getRightMostTuple(lpage), lpage, lblkno);
 725         if (PageAddItem(root, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
 726                 elog(ERROR, "failed to add item to index root page");
 727         pfree(itup);
 728
 729         itup = GinFormInteriorTuple(getRightMostTuple(rpage), rpage, rblkno);
 730         if (PageAddItem(root, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
 731                 elog(ERROR, "failed to add item to index root page");
 732         pfree(itup);
 733 }
 734
 735 /*
 736  * Set up GinBtree for entry page access
 737  *
 738  * Note: during WAL recovery, there may be no valid data in ginstate
 739  * other than a faked-up Relation pointer; the key datum is bogus too.
 740  */
 741 void
 742 ginPrepareEntryScan(GinBtree btree, OffsetNumber attnum,
 743                                         Datum key, GinNullCategory category,
 744                                         GinState *ginstate)
 745 {
 746         memset(btree, 0, sizeof(GinBtreeData));
 747
 748         btree->index = ginstate->index;
 749         btree->rootBlkno = GIN_ROOT_BLKNO;
 750         btree->ginstate = ginstate;
 751
 752         btree->findChildPage = entryLocateEntry;
 753         btree->getLeftMostChild = entryGetLeftMostPage;
 754         btree->isMoveRight = entryIsMoveRight;
 755         btree->findItem = entryLocateLeafEntry;
 756         btree->findChildPtr = entryFindChildPtr;
 757         btree->placeToPage = entryPlaceToPage;
 758         btree->fillRoot = ginEntryFillRoot;
 759         btree->prepareDownlink = entryPrepareDownlink;
 760
 761         btree->isData = FALSE;
 762         btree->fullScan = FALSE;
 763         btree->isBuild = FALSE;
 764
 765         btree->entryAttnum = attnum;
 766         btree->entryKey = key;
 767         btree->entryCategory = category;
 768 }