diff options
Diffstat (limited to 'src/backend/access/nbtree')
| -rw-r--r-- | src/backend/access/nbtree/nbtcompare.c | 11 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtinsert.c | 606 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtpage.c | 60 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtree.c | 271 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtsearch.c | 93 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtsort.c | 103 | ||||
| -rw-r--r-- | src/backend/access/nbtree/nbtutils.c | 49 |
7 files changed, 632 insertions, 561 deletions
diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c index 435a7f72dde..fc85906d9b2 100644 --- a/src/backend/access/nbtree/nbtcompare.c +++ b/src/backend/access/nbtree/nbtcompare.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtcompare.c,v 1.40 2001/01/24 19:42:48 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtcompare.c,v 1.41 2001/03/22 03:59:14 momjian Exp $ * * NOTES * @@ -150,8 +150,8 @@ btoidvectorcmp(PG_FUNCTION_ARGS) Datum btabstimecmp(PG_FUNCTION_ARGS) { - AbsoluteTime a = PG_GETARG_ABSOLUTETIME(0); - AbsoluteTime b = PG_GETARG_ABSOLUTETIME(1); + AbsoluteTime a = PG_GETARG_ABSOLUTETIME(0); + AbsoluteTime b = PG_GETARG_ABSOLUTETIME(1); if (AbsoluteTimeIsBefore(a, b)) PG_RETURN_INT32(-1); @@ -236,9 +236,10 @@ bttextcmp(PG_FUNCTION_ARGS) if (res == 0 && VARSIZE(a) != VARSIZE(b)) { + /* - * The two strings are the same in the first len bytes, - * and they are of different lengths. + * The two strings are the same in the first len bytes, and they + * are of different lengths. */ if (VARSIZE(a) < VARSIZE(b)) res = -1; diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c index 325e585e3cc..f2112de6777 100644 --- a/src/backend/access/nbtree/nbtinsert.c +++ b/src/backend/access/nbtree/nbtinsert.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.81 2001/02/07 23:35:33 vadim Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.82 2001/03/22 03:59:14 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -23,23 +23,23 @@ typedef struct { /* context data for _bt_checksplitloc */ - Size newitemsz; /* size of new item to be inserted */ - bool non_leaf; /* T if splitting an internal node */ + Size newitemsz; /* size of new item to be inserted */ + bool non_leaf; /* T if splitting an internal node */ - bool have_split; /* found a valid split? */ + bool have_split; /* found a valid split? */ /* these fields valid only if have_split is true */ - bool newitemonleft; /* new item on left or right of best split */ + bool newitemonleft; /* new item on left or right of best split */ OffsetNumber firstright; /* best split point */ - int best_delta; /* best size delta so far */ + int best_delta; /* best size delta so far */ } FindSplitData; extern bool FixBTree; -Buffer _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release); +Buffer _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release); static void _bt_fixtree(Relation rel, BlockNumber blkno); -static void _bt_fixbranch(Relation rel, BlockNumber lblkno, - BlockNumber rblkno, BTStack true_stack); +static void _bt_fixbranch(Relation rel, BlockNumber lblkno, + BlockNumber rblkno, BTStack true_stack); static void _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit); static void _bt_fixup(Relation rel, Buffer buf); static OffsetNumber _bt_getoff(Page page, BlockNumber blkno); @@ -47,34 +47,34 @@ static OffsetNumber _bt_getoff(Page page, BlockNumber blkno); static Buffer _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf); static TransactionId _bt_check_unique(Relation rel, BTItem btitem, - Relation heapRel, Buffer buf, - ScanKey itup_scankey); + Relation heapRel, Buffer buf, + ScanKey itup_scankey); static InsertIndexResult _bt_insertonpg(Relation rel, Buffer buf, - BTStack stack, - int keysz, ScanKey scankey, - BTItem btitem, - OffsetNumber afteritem); -static void _bt_insertuple(Relation rel, Buffer buf, - Size itemsz, BTItem btitem, OffsetNumber newitemoff); + BTStack stack, + int keysz, ScanKey scankey, + BTItem btitem, + OffsetNumber afteritem); +static void _bt_insertuple(Relation rel, Buffer buf, + Size itemsz, BTItem btitem, OffsetNumber newitemoff); static Buffer _bt_split(Relation rel, Buffer buf, OffsetNumber firstright, - OffsetNumber newitemoff, Size newitemsz, - BTItem newitem, bool newitemonleft, - OffsetNumber *itup_off, BlockNumber *itup_blkno); + OffsetNumber newitemoff, Size newitemsz, + BTItem newitem, bool newitemonleft, + OffsetNumber *itup_off, BlockNumber *itup_blkno); static OffsetNumber _bt_findsplitloc(Relation rel, Page page, - OffsetNumber newitemoff, - Size newitemsz, - bool *newitemonleft); + OffsetNumber newitemoff, + Size newitemsz, + bool *newitemonleft); static void _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright, - int leftfree, int rightfree, - bool newitemonleft, Size firstrightitemsz); + int leftfree, int rightfree, + bool newitemonleft, Size firstrightitemsz); static Buffer _bt_getstackbuf(Relation rel, BTStack stack, int access); static void _bt_pgaddtup(Relation rel, Page page, - Size itemsize, BTItem btitem, - OffsetNumber itup_off, const char *where); + Size itemsize, BTItem btitem, + OffsetNumber itup_off, const char *where); static bool _bt_isequal(TupleDesc itupdesc, Page page, OffsetNumber offnum, - int keysz, ScanKey scankey); + int keysz, ScanKey scankey); -static Relation _xlheapRel; /* temporary hack */ +static Relation _xlheapRel; /* temporary hack */ /* * _bt_doinsert() -- Handle insertion of a single btitem in the tree. @@ -114,8 +114,8 @@ top: buf = _bt_moveright(rel, buf, natts, itup_scankey, BT_WRITE); /* - * If we're not allowing duplicates, make sure the key isn't - * already in the index. XXX this belongs somewhere else, likely + * If we're not allowing duplicates, make sure the key isn't already + * in the index. XXX this belongs somewhere else, likely */ if (index_is_unique) { @@ -134,7 +134,7 @@ top: } } - _xlheapRel = heapRel; /* temporary hack */ + _xlheapRel = heapRel; /* temporary hack */ /* do the insertion */ res = _bt_insertonpg(rel, buf, stack, natts, itup_scankey, btitem, 0); @@ -150,7 +150,7 @@ top: * _bt_check_unique() -- Check for violation of unique index constraint * * Returns NullTransactionId if there is no conflict, else an xact ID we - * must wait for to see if it commits a conflicting tuple. If an actual + * must wait for to see if it commits a conflicting tuple. If an actual * conflict is detected, no return --- just elog(). */ static TransactionId @@ -171,8 +171,8 @@ _bt_check_unique(Relation rel, BTItem btitem, Relation heapRel, maxoff = PageGetMaxOffsetNumber(page); /* - * Find first item >= proposed new item. Note we could also get - * a pointer to end-of-page here. + * Find first item >= proposed new item. Note we could also get a + * pointer to end-of-page here. */ offset = _bt_binsrch(rel, buf, natts, itup_scankey); @@ -187,24 +187,24 @@ _bt_check_unique(Relation rel, BTItem btitem, Relation heapRel, BlockNumber nblkno; /* - * _bt_compare returns 0 for (1,NULL) and (1,NULL) - this's - * how we handling NULLs - and so we must not use _bt_compare - * in real comparison, but only for ordering/finding items on - * pages. - vadim 03/24/97 + * _bt_compare returns 0 for (1,NULL) and (1,NULL) - this's how we + * handling NULLs - and so we must not use _bt_compare in real + * comparison, but only for ordering/finding items on pages. - + * vadim 03/24/97 * - * make sure the offset points to an actual key - * before trying to compare it... + * make sure the offset points to an actual key before trying to + * compare it... */ if (offset <= maxoff) { - if (! _bt_isequal(itupdesc, page, offset, natts, itup_scankey)) + if (!_bt_isequal(itupdesc, page, offset, natts, itup_scankey)) break; /* we're past all the equal tuples */ /* - * Have to check is inserted heap tuple deleted one (i.e. - * just moved to another place by vacuum)! We only need to - * do this once, but don't want to do it at all unless - * we see equal tuples, so as not to slow down unequal case. + * Have to check is inserted heap tuple deleted one (i.e. just + * moved to another place by vacuum)! We only need to do this + * once, but don't want to do it at all unless we see equal + * tuples, so as not to slow down unequal case. */ if (chtup) { @@ -220,11 +220,11 @@ _bt_check_unique(Relation rel, BTItem btitem, Relation heapRel, cbti = (BTItem) PageGetItem(page, PageGetItemId(page, offset)); htup.t_self = cbti->bti_itup.t_tid; heap_fetch(heapRel, SnapshotDirty, &htup, &buffer); - if (htup.t_data != NULL) /* it is a duplicate */ + if (htup.t_data != NULL) /* it is a duplicate */ { TransactionId xwait = - (TransactionIdIsValid(SnapshotDirty->xmin)) ? - SnapshotDirty->xmin : SnapshotDirty->xmax; + (TransactionIdIsValid(SnapshotDirty->xmin)) ? + SnapshotDirty->xmin : SnapshotDirty->xmax; /* * If this tuple is being updated by other transaction @@ -238,6 +238,7 @@ _bt_check_unique(Relation rel, BTItem btitem, Relation heapRel, /* Tell _bt_doinsert to wait... */ return xwait; } + /* * Otherwise we have a definite conflict. */ @@ -304,7 +305,7 @@ _bt_check_unique(Relation rel, BTItem btitem, Relation heapRel, * NOTE: if the new key is equal to one or more existing keys, we can * legitimately place it anywhere in the series of equal keys --- in fact, * if the new key is equal to the page's "high key" we can place it on - * the next page. If it is equal to the high key, and there's not room + * the next page. If it is equal to the high key, and there's not room * to insert the new tuple on the current page without splitting, then * we can move right hoping to find more free space and avoid a split. * (We should not move right indefinitely, however, since that leads to @@ -358,16 +359,14 @@ _bt_insertonpg(Relation rel, */ if (itemsz > (PageGetPageSize(page) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) / 3 - sizeof(ItemIdData)) elog(ERROR, "btree: index item size %lu exceeds maximum %lu", - (unsigned long)itemsz, - (PageGetPageSize(page) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) /3 - sizeof(ItemIdData)); + (unsigned long) itemsz, + (PageGetPageSize(page) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) / 3 - sizeof(ItemIdData)); /* * Determine exactly where new item will go. */ if (afteritem > 0) - { newitemoff = afteritem + 1; - } else { /*---------- @@ -383,12 +382,12 @@ _bt_insertonpg(Relation rel, * on every insert. We implement "get tired" as a random choice, * since stopping after scanning a fixed number of pages wouldn't work * well (we'd never reach the right-hand side of previously split - * pages). Currently the probability of moving right is set at 0.99, + * pages). Currently the probability of moving right is set at 0.99, * which may seem too high to change the behavior much, but it does an * excellent job of preventing O(N^2) behavior with many equal keys. *---------- */ - bool movedright = false; + bool movedright = false; while (PageGetFreeSpace(page) < itemsz && !P_RIGHTMOST(lpageop) && @@ -396,7 +395,7 @@ _bt_insertonpg(Relation rel, random() > (MAX_RANDOM_VALUE / 100)) { /* step right one page */ - BlockNumber rblkno = lpageop->btpo_next; + BlockNumber rblkno = lpageop->btpo_next; _bt_relbuf(rel, buf, BT_WRITE); buf = _bt_getbuf(rel, rblkno, BT_WRITE); @@ -404,10 +403,11 @@ _bt_insertonpg(Relation rel, lpageop = (BTPageOpaque) PageGetSpecialPointer(page); movedright = true; } + /* - * Now we are on the right page, so find the insert position. - * If we moved right at all, we know we should insert at the - * start of the page, else must find the position by searching. + * Now we are on the right page, so find the insert position. If + * we moved right at all, we know we should insert at the start of + * the page, else must find the position by searching. */ if (movedright) newitemoff = P_FIRSTDATAKEY(lpageop); @@ -418,9 +418,9 @@ _bt_insertonpg(Relation rel, /* * Do we need to split the page to fit the item on it? * - * Note: PageGetFreeSpace() subtracts sizeof(ItemIdData) from its - * result, so this comparison is correct even though we appear to - * be accounting only for the item and not for its line pointer. + * Note: PageGetFreeSpace() subtracts sizeof(ItemIdData) from its result, + * so this comparison is correct even though we appear to be + * accounting only for the item and not for its line pointer. */ if (PageGetFreeSpace(page) < itemsz) { @@ -468,7 +468,7 @@ _bt_insertonpg(Relation rel, if (is_root) { - Buffer rootbuf; + Buffer rootbuf; Assert(stack == (BTStack) NULL); /* create a new root node and release the split buffers */ @@ -481,7 +481,7 @@ _bt_insertonpg(Relation rel, { InsertIndexResult newres; BTItem new_item; - BTStackData fakestack; + BTStackData fakestack; BTItem ritem; Buffer pbuf; @@ -489,10 +489,11 @@ _bt_insertonpg(Relation rel, if (stack == (BTStack) NULL) { elog(DEBUG, "btree: concurrent ROOT page split"); + /* * If root page splitter failed to create new root page - * then old root' btpo_parent still points to metapage. - * We have to fix root page in this case. + * then old root' btpo_parent still points to metapage. We + * have to fix root page in this case. */ if (BTreeInvalidParent(lpageop)) { @@ -531,9 +532,9 @@ _bt_insertonpg(Relation rel, * item! We want to find parent pointing to where we are, * right ? - vadim 05/27/97 * - * Interestingly, this means we didn't *really* need to stack - * the parent key at all; all we really care about is the - * saved block and offset as a starting point for our search... + * Interestingly, this means we didn't *really* need to stack the + * parent key at all; all we really care about is the saved + * block and offset as a starting point for our search... */ ItemPointerSet(&(stack->bts_btitem.bti_itup.t_tid), bknum, P_HIKEY); @@ -583,25 +584,26 @@ formres:; } static void -_bt_insertuple(Relation rel, Buffer buf, - Size itemsz, BTItem btitem, OffsetNumber newitemoff) +_bt_insertuple(Relation rel, Buffer buf, + Size itemsz, BTItem btitem, OffsetNumber newitemoff) { - Page page = BufferGetPage(buf); - BTPageOpaque pageop = (BTPageOpaque) PageGetSpecialPointer(page); + Page page = BufferGetPage(buf); + BTPageOpaque pageop = (BTPageOpaque) PageGetSpecialPointer(page); START_CRIT_SECTION(); _bt_pgaddtup(rel, page, itemsz, btitem, newitemoff, "page"); /* XLOG stuff */ { - xl_btree_insert xlrec; - uint8 flag = XLOG_BTREE_INSERT; - XLogRecPtr recptr; - XLogRecData rdata[2]; - BTItemData truncitem; - xlrec.target.node = rel->rd_node; + xl_btree_insert xlrec; + uint8 flag = XLOG_BTREE_INSERT; + XLogRecPtr recptr; + XLogRecData rdata[2]; + BTItemData truncitem; + + xlrec.target.node = rel->rd_node; ItemPointerSet(&(xlrec.target.tid), BufferGetBlockNumber(buf), newitemoff); rdata[0].buffer = InvalidBuffer; - rdata[0].data = (char*)&xlrec; + rdata[0].data = (char *) &xlrec; rdata[0].len = SizeOfBtreeInsert; rdata[0].next = &(rdata[1]); @@ -610,14 +612,14 @@ _bt_insertuple(Relation rel, Buffer buf, { truncitem = *btitem; truncitem.bti_itup.t_info = sizeof(BTItemData); - rdata[1].data = (char*)&truncitem; + rdata[1].data = (char *) &truncitem; rdata[1].len = sizeof(BTItemData); } else { - rdata[1].data = (char*)btitem; - rdata[1].len = IndexTupleDSize(btitem->bti_itup) + - (sizeof(BTItemData) - sizeof(IndexTupleData)); + rdata[1].data = (char *) btitem; + rdata[1].len = IndexTupleDSize(btitem->bti_itup) + + (sizeof(BTItemData) - sizeof(IndexTupleData)); } rdata[1].buffer = buf; rdata[1].next = NULL; @@ -700,8 +702,8 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright, /* * If the page we're splitting is not the rightmost page at its level - * in the tree, then the first entry on the page is the high key - * for the page. We need to copy that to the right half. Otherwise + * in the tree, then the first entry on the page is the high key for + * the page. We need to copy that to the right half. Otherwise * (meaning the rightmost page case), all the items on the right half * will be user data. */ @@ -779,13 +781,13 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright, if (i < firstright) { _bt_pgaddtup(rel, leftpage, itemsz, item, leftoff, - "left sibling"); + "left sibling"); leftoff = OffsetNumberNext(leftoff); } else { _bt_pgaddtup(rel, rightpage, itemsz, item, rightoff, - "right sibling"); + "right sibling"); rightoff = OffsetNumberNext(rightoff); } } @@ -812,11 +814,11 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright, } /* - * We have to grab the right sibling (if any) and fix the prev - * pointer there. We are guaranteed that this is deadlock-free - * since no other writer will be holding a lock on that page - * and trying to move left, and all readers release locks on a page - * before trying to fetch its neighbors. + * We have to grab the right sibling (if any) and fix the prev pointer + * there. We are guaranteed that this is deadlock-free since no other + * writer will be holding a lock on that page and trying to move left, + * and all readers release locks on a page before trying to fetch its + * neighbors. */ if (!P_RIGHTMOST(ropaque)) @@ -834,12 +836,12 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright, */ START_CRIT_SECTION(); { - xl_btree_split xlrec; - int flag = (newitemonleft) ? - XLOG_BTREE_SPLEFT : XLOG_BTREE_SPLIT; - BlockNumber blkno; - XLogRecPtr recptr; - XLogRecData rdata[4]; + xl_btree_split xlrec; + int flag = (newitemonleft) ? + XLOG_BTREE_SPLEFT : XLOG_BTREE_SPLIT; + BlockNumber blkno; + XLogRecPtr recptr; + XLogRecData rdata[4]; xlrec.target.node = rel->rd_node; ItemPointerSet(&(xlrec.target.tid), *itup_blkno, *itup_off); @@ -856,31 +858,33 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright, BlockIdSet(&(xlrec.parentblk), lopaque->btpo_parent); BlockIdSet(&(xlrec.leftblk), lopaque->btpo_prev); BlockIdSet(&(xlrec.rightblk), ropaque->btpo_next); - /* - * Dirrect access to page is not good but faster - we should + + /* + * Dirrect access to page is not good but faster - we should * implement some new func in page API. */ - xlrec.leftlen = ((PageHeader)leftpage)->pd_special - - ((PageHeader)leftpage)->pd_upper; + xlrec.leftlen = ((PageHeader) leftpage)->pd_special - + ((PageHeader) leftpage)->pd_upper; rdata[0].buffer = InvalidBuffer; - rdata[0].data = (char*)&xlrec; + rdata[0].data = (char *) &xlrec; rdata[0].len = SizeOfBtreeSplit; rdata[0].next = &(rdata[1]); rdata[1].buffer = InvalidBuffer; - rdata[1].data = (char*)leftpage + ((PageHeader)leftpage)->pd_upper; + rdata[1].data = (char *) leftpage + ((PageHeader) leftpage)->pd_upper; rdata[1].len = xlrec.leftlen; rdata[1].next = &(rdata[2]); rdata[2].buffer = InvalidBuffer; - rdata[2].data = (char*)rightpage + ((PageHeader)rightpage)->pd_upper; - rdata[2].len = ((PageHeader)rightpage)->pd_special - - ((PageHeader)rightpage)->pd_upper; + rdata[2].data = (char *) rightpage + ((PageHeader) rightpage)->pd_upper; + rdata[2].len = ((PageHeader) rightpage)->pd_special - + ((PageHeader) rightpage)->pd_upper; rdata[2].next = NULL; if (!P_RIGHTMOST(ropaque)) { - BTPageOpaque sopaque = (BTPageOpaque) PageGetSpecialPointer(spage); + BTPageOpaque sopaque = (BTPageOpaque) PageGetSpecialPointer(spage); + sopaque->btpo_prev = BufferGetBlockNumber(rbuf); rdata[2].next = &(rdata[3]); @@ -942,7 +946,7 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright, * * We return the index of the first existing tuple that should go on the * righthand page, plus a boolean indicating whether the new tuple goes on - * the left or right page. The bool is necessary to disambiguate the case + * the left or right page. The bool is necessary to disambiguate the case * where firstright == newitemoff. */ static OffsetNumber @@ -968,23 +972,23 @@ _bt_findsplitloc(Relation rel, /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */ newitemsz += sizeof(ItemIdData); state.newitemsz = newitemsz; - state.non_leaf = ! P_ISLEAF(opaque); + state.non_leaf = !P_ISLEAF(opaque); state.have_split = false; /* Total free space available on a btree page, after fixed overhead */ leftspace = rightspace = PageGetPageSize(page) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData)) - + sizeof(ItemIdData); + +sizeof(ItemIdData); /* - * Finding the best possible split would require checking all the possible - * split points, because of the high-key and left-key special cases. - * That's probably more work than it's worth; instead, stop as soon as - * we find a "good-enough" split, where good-enough is defined as an - * imbalance in free space of no more than pagesize/16 (arbitrary...) - * This should let us stop near the middle on most pages, instead of - * plowing to the end. + * Finding the best possible split would require checking all the + * possible split points, because of the high-key and left-key special + * cases. That's probably more work than it's worth; instead, stop as + * soon as we find a "good-enough" split, where good-enough is defined + * as an imbalance in free space of no more than pagesize/16 + * (arbitrary...) This should let us stop near the middle on most + * pages, instead of plowing to the end. */ goodenough = leftspace / 16; @@ -1024,6 +1028,7 @@ _bt_findsplitloc(Relation rel, */ leftfree = leftspace - dataitemstoleft - (int) itemsz; rightfree = rightspace - (dataitemtotal - dataitemstoleft); + /* * Will the new item go to left or right of split? */ @@ -1051,10 +1056,10 @@ _bt_findsplitloc(Relation rel, } /* - * I believe it is not possible to fail to find a feasible split, - * but just in case ... + * I believe it is not possible to fail to find a feasible split, but + * just in case ... */ - if (! state.have_split) + if (!state.have_split) elog(FATAL, "_bt_findsplitloc: can't find a feasible split point for %s", RelationGetRelationName(rel)); @@ -1071,6 +1076,7 @@ _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright, int leftfree, int rightfree, bool newitemonleft, Size firstrightitemsz) { + /* * Account for the new item on whichever side it is to be put. */ @@ -1078,19 +1084,21 @@ _bt_checksplitloc(FindSplitData *state, OffsetNumber firstright, leftfree -= (int) state->newitemsz; else rightfree -= (int) state->newitemsz; + /* - * If we are not on the leaf level, we will be able to discard the - * key data from the first item that winds up on the right page. + * If we are not on the leaf level, we will be able to discard the key + * data from the first item that winds up on the right page. */ if (state->non_leaf) rightfree += (int) firstrightitemsz - (int) (MAXALIGN(sizeof(BTItemData)) + sizeof(ItemIdData)); + /* * If feasible split point, remember best delta. */ if (leftfree >= 0 && rightfree >= 0) { - int delta = leftfree - rightfree; + int delta = leftfree - rightfree; if (delta < 0) delta = -delta; @@ -1134,10 +1142,11 @@ _bt_getstackbuf(Relation rel, BTStack stack, int access) maxoff = PageGetMaxOffsetNumber(page); start = stack->bts_offset; + /* - * _bt_insertonpg set bts_offset to InvalidOffsetNumber in the - * case of concurrent ROOT page split. Also, watch out for - * possibility that page has a high key now when it didn't before. + * _bt_insertonpg set bts_offset to InvalidOffsetNumber in the case of + * concurrent ROOT page split. Also, watch out for possibility that + * page has a high key now when it didn't before. */ if (start < P_FIRSTDATAKEY(opaque)) start = P_FIRSTDATAKEY(opaque); @@ -1159,11 +1168,15 @@ _bt_getstackbuf(Relation rel, BTStack stack, int access) return buf; } } - /* by here, the item we're looking for moved right at least one page */ + + /* + * by here, the item we're looking for moved right at least one + * page + */ if (P_RIGHTMOST(opaque)) { _bt_relbuf(rel, buf, access); - return(InvalidBuffer); + return (InvalidBuffer); } blkno = opaque->btpo_next; @@ -1190,27 +1203,27 @@ _bt_getstackbuf(Relation rel, BTStack stack, int access) * * On entry, lbuf (the old root) and rbuf (its new peer) are write- * locked. On exit, a new root page exists with entries for the - * two new children, metapage is updated and unlocked/unpinned. - * The new root buffer is returned to caller which has to unlock/unpin - * lbuf, rbuf & rootbuf. + * two new children, metapage is updated and unlocked/unpinned. + * The new root buffer is returned to caller which has to unlock/unpin + * lbuf, rbuf & rootbuf. */ static Buffer _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf) { - Buffer rootbuf; - Page lpage, - rpage, - rootpage; - BlockNumber lbkno, - rbkno; - BlockNumber rootblknum; - BTPageOpaque rootopaque; - ItemId itemid; - BTItem item; - Size itemsz; - BTItem new_item; - Buffer metabuf; - Page metapg; + Buffer rootbuf; + Page lpage, + rpage, + rootpage; + BlockNumber lbkno, + rbkno; + BlockNumber rootblknum; + BTPageOpaque rootopaque; + ItemId itemid; + BTItem item; + Size itemsz; + BTItem new_item; + Buffer metabuf; + Page metapg; BTMetaPageData *metad; /* get a new root page */ @@ -1236,9 +1249,9 @@ _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf) rpage = BufferGetPage(rbuf); /* - * Make sure pages in old root level have valid parent links --- we will - * need this in _bt_insertonpg() if a concurrent root split happens (see - * README). + * Make sure pages in old root level have valid parent links --- we + * will need this in _bt_insertonpg() if a concurrent root split + * happens (see README). */ ((BTPageOpaque) PageGetSpecialPointer(lpage))->btpo_parent = ((BTPageOpaque) PageGetSpecialPointer(rpage))->btpo_parent = @@ -1264,8 +1277,8 @@ _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf) pfree(new_item); /* - * Create downlink item for right page. The key for it is obtained from - * the "high key" position in the left page. + * Create downlink item for right page. The key for it is obtained + * from the "high key" position in the left page. */ itemid = PageGetItemId(lpage, P_HIKEY); itemsz = ItemIdGetLength(itemid); @@ -1285,26 +1298,26 @@ _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf) /* XLOG stuff */ { - xl_btree_newroot xlrec; - XLogRecPtr recptr; - XLogRecData rdata[2]; + xl_btree_newroot xlrec; + XLogRecPtr recptr; + XLogRecData rdata[2]; xlrec.node = rel->rd_node; xlrec.level = metad->btm_level; BlockIdSet(&(xlrec.rootblk), rootblknum); rdata[0].buffer = InvalidBuffer; - rdata[0].data = (char*)&xlrec; + rdata[0].data = (char *) &xlrec; rdata[0].len = SizeOfBtreeNewroot; rdata[0].next = &(rdata[1]); - /* - * Dirrect access to page is not good but faster - we should + /* + * Dirrect access to page is not good but faster - we should * implement some new func in page API. */ rdata[1].buffer = InvalidBuffer; - rdata[1].data = (char*)rootpage + ((PageHeader) rootpage)->pd_upper; - rdata[1].len = ((PageHeader)rootpage)->pd_special - - ((PageHeader)rootpage)->pd_upper; + rdata[1].data = (char *) rootpage + ((PageHeader) rootpage)->pd_upper; + rdata[1].len = ((PageHeader) rootpage)->pd_special - + ((PageHeader) rootpage)->pd_upper; rdata[1].next = NULL; recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_NEWROOT, rdata); @@ -1325,7 +1338,7 @@ _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf) /* write and let go of metapage buffer */ _bt_wrtbuf(rel, metabuf); - return(rootbuf); + return (rootbuf); } /* @@ -1339,24 +1352,31 @@ _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf) Buffer _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release) { - Buffer rootbuf; - BlockNumber rootblk; - Page rootpage; - XLogRecPtr rootLSN; - Page oldrootpage = BufferGetPage(oldrootbuf); - BTPageOpaque oldrootopaque = (BTPageOpaque) - PageGetSpecialPointer(oldrootpage); - Buffer buf, leftbuf, rightbuf; - Page page, leftpage, rightpage; - BTPageOpaque opaque, leftopaque, rightopaque; - OffsetNumber newitemoff; - BTItem btitem, ritem; - Size itemsz; - - if (! P_LEFTMOST(oldrootopaque) || P_RIGHTMOST(oldrootopaque)) + Buffer rootbuf; + BlockNumber rootblk; + Page rootpage; + XLogRecPtr rootLSN; + Page oldrootpage = BufferGetPage(oldrootbuf); + BTPageOpaque oldrootopaque = (BTPageOpaque) + PageGetSpecialPointer(oldrootpage); + Buffer buf, + leftbuf, + rightbuf; + Page page, + leftpage, + rightpage; + BTPageOpaque opaque, + leftopaque, + rightopaque; + OffsetNumber newitemoff; + BTItem btitem, + ritem; + Size itemsz; + + if (!P_LEFTMOST(oldrootopaque) || P_RIGHTMOST(oldrootopaque)) elog(ERROR, "bt_fixroot: not valid old root page"); - /* Read right neighbor and create new root page*/ + /* Read right neighbor and create new root page */ leftbuf = _bt_getbuf(rel, oldrootopaque->btpo_next, BT_WRITE); leftpage = BufferGetPage(leftbuf); leftopaque = (BTPageOpaque) PageGetSpecialPointer(leftpage); @@ -1377,26 +1397,26 @@ _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release) * * If concurrent process will split one of pages on this level then it * will see either btpo_parent == metablock or btpo_parent == rootblk. - * In first case it will give up its locks and walk to the leftmost page - * (oldrootbuf) in _bt_fixup() - ie it will wait for us and let us - * continue. In second case it will try to lock rootbuf keeping its locks - * on buffers we already passed, also waiting for us. If we'll have to - * unlock rootbuf (split it) and that process will have to split page - * of new level we created (level of rootbuf) then it will wait while - * we create upper level. Etc. + * In first case it will give up its locks and walk to the leftmost + * page (oldrootbuf) in _bt_fixup() - ie it will wait for us and let + * us continue. In second case it will try to lock rootbuf keeping its + * locks on buffers we already passed, also waiting for us. If we'll + * have to unlock rootbuf (split it) and that process will have to + * split page of new level we created (level of rootbuf) then it will + * wait while we create upper level. Etc. */ - while(! P_RIGHTMOST(leftopaque)) + while (!P_RIGHTMOST(leftopaque)) { rightbuf = _bt_getbuf(rel, leftopaque->btpo_next, BT_WRITE); rightpage = BufferGetPage(rightbuf); rightopaque = (BTPageOpaque) PageGetSpecialPointer(rightpage); /* - * Update LSN & StartUpID of child page buffer to ensure that - * it will be written on disk after flushing log record for new - * root creation. Unfortunately, for the moment (?) we do not - * log this operation and so possibly break our rule to log entire - * page content on first after checkpoint modification. + * Update LSN & StartUpID of child page buffer to ensure that it + * will be written on disk after flushing log record for new root + * creation. Unfortunately, for the moment (?) we do not log this + * operation and so possibly break our rule to log entire page + * content on first after checkpoint modification. */ HOLD_INTERRUPTS(); rightopaque->btpo_parent = rootblk; @@ -1416,17 +1436,17 @@ _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release) if (PageGetFreeSpace(page) < itemsz) { - Buffer newbuf; - OffsetNumber firstright; - OffsetNumber itup_off; - BlockNumber itup_blkno; - bool newitemonleft; + Buffer newbuf; + OffsetNumber firstright; + OffsetNumber itup_off; + BlockNumber itup_blkno; + bool newitemonleft; firstright = _bt_findsplitloc(rel, page, - newitemoff, itemsz, &newitemonleft); + newitemoff, itemsz, &newitemonleft); newbuf = _bt_split(rel, buf, firstright, - newitemoff, itemsz, btitem, newitemonleft, - &itup_off, &itup_blkno); + newitemoff, itemsz, btitem, newitemonleft, + &itup_off, &itup_blkno); /* Keep lock on new "root" buffer ! */ if (buf != rootbuf) _bt_relbuf(rel, buf, BT_WRITE); @@ -1450,10 +1470,10 @@ _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release) /* * Here we hold locks on old root buffer, new root buffer we've - * created with _bt_newroot() - rootbuf, - and buf we've used - * for last insert ops - buf. If rootbuf != buf then we have to - * create at least one more level. And if "release" is TRUE - * then we give up oldrootbuf. + * created with _bt_newroot() - rootbuf, - and buf we've used for last + * insert ops - buf. If rootbuf != buf then we have to create at least + * one more level. And if "release" is TRUE then we give up + * oldrootbuf. */ if (release) _bt_wrtbuf(rel, oldrootbuf); @@ -1461,10 +1481,10 @@ _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release) if (rootbuf != buf) { _bt_wrtbuf(rel, buf); - return(_bt_fixroot(rel, rootbuf, true)); + return (_bt_fixroot(rel, rootbuf, true)); } - return(rootbuf); + return (rootbuf); } /* @@ -1474,17 +1494,17 @@ _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release) static void _bt_fixtree(Relation rel, BlockNumber blkno) { - Buffer buf; - Page page; - BTPageOpaque opaque; - BlockNumber pblkno; + Buffer buf; + Page page; + BTPageOpaque opaque; + BlockNumber pblkno; - for ( ; ; ) + for (;;) { buf = _bt_getbuf(rel, blkno, BT_READ); page = BufferGetPage(buf); opaque = (BTPageOpaque) PageGetSpecialPointer(page); - if (! P_LEFTMOST(opaque) || P_ISLEAF(opaque)) + if (!P_LEFTMOST(opaque) || P_ISLEAF(opaque)) elog(ERROR, "bt_fixtree[%s]: invalid start page (need to recreate index)", RelationGetRelationName(rel)); pblkno = opaque->btpo_parent; @@ -1534,25 +1554,26 @@ _bt_fixtree(Relation rel, BlockNumber blkno) static void _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) { - BlockNumber blkno = BufferGetBlockNumber(buf); - Page page; - BTPageOpaque opaque; - BlockNumber cblkno[3]; - OffsetNumber coff[3]; - Buffer cbuf[3]; - Page cpage[3]; - BTPageOpaque copaque[3]; - BTItem btitem; - int cidx, i; - bool goodbye = false; - char tbuf[BLCKSZ]; + BlockNumber blkno = BufferGetBlockNumber(buf); + Page page; + BTPageOpaque opaque; + BlockNumber cblkno[3]; + OffsetNumber coff[3]; + Buffer cbuf[3]; + Page cpage[3]; + BTPageOpaque copaque[3]; + BTItem btitem; + int cidx, + i; + bool goodbye = false; + char tbuf[BLCKSZ]; page = BufferGetPage(buf); /* copy page to temp storage */ memmove(tbuf, page, PageGetPageSize(page)); _bt_relbuf(rel, buf, BT_READ); - page = (Page)tbuf; + page = (Page) tbuf; opaque = (BTPageOpaque) PageGetSpecialPointer(page); /* Initialize first child data */ @@ -1564,20 +1585,21 @@ _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) cbuf[0] = _bt_getbuf(rel, cblkno[0], BT_READ); cpage[0] = BufferGetPage(cbuf[0]); copaque[0] = (BTPageOpaque) PageGetSpecialPointer(cpage[0]); - if (P_LEFTMOST(opaque) && ! P_LEFTMOST(copaque[0])) + if (P_LEFTMOST(opaque) && !P_LEFTMOST(copaque[0])) elog(ERROR, "bt_fixtlevel[%s]: non-leftmost child page of leftmost parent (need to recreate index)", RelationGetRelationName(rel)); /* caller should take care and avoid this */ if (P_RIGHTMOST(copaque[0])) elog(ERROR, "bt_fixtlevel[%s]: invalid start child (need to recreate index)", RelationGetRelationName(rel)); - for ( ; ; ) + for (;;) { + /* - * Read up to 2 more child pages and look for pointers - * to them in *saved* parent page + * Read up to 2 more child pages and look for pointers to them in + * *saved* parent page */ coff[1] = coff[2] = InvalidOffsetNumber; - for (cidx = 0; cidx < 2; ) + for (cidx = 0; cidx < 2;) { cidx++; cblkno[cidx] = (copaque[cidx - 1])->btpo_next; @@ -1609,20 +1631,20 @@ _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) if (coff[1] == InvalidOffsetNumber || (cidx == 2 && coff[2] == InvalidOffsetNumber)) { - Buffer newbuf; - Page newpage; - BTPageOpaque newopaque; - BTItem ritem; - Size itemsz; - OffsetNumber newitemoff; - BlockNumber parblk[3]; - BTStackData stack; + Buffer newbuf; + Page newpage; + BTPageOpaque newopaque; + BTItem ritem; + Size itemsz; + OffsetNumber newitemoff; + BlockNumber parblk[3]; + BTStackData stack; stack.bts_parent = NULL; stack.bts_blkno = blkno; stack.bts_offset = InvalidOffsetNumber; ItemPointerSet(&(stack.bts_btitem.bti_itup.t_tid), - cblkno[0], P_HIKEY); + cblkno[0], P_HIKEY); buf = _bt_getstackbuf(rel, &stack, BT_WRITE); if (buf == InvalidBuffer) @@ -1644,19 +1666,19 @@ _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) if (coff[i] != InvalidOffsetNumber) { if (parblk[i] == parblk[i - 1] && - coff[i] != coff[i - 1] + 1) + coff[i] != coff[i - 1] + 1) elog(ERROR, "bt_fixlevel[%s]: invalid item order(2) (need to recreate index)", RelationGetRelationName(rel)); continue; } /* Have to check next page ? */ - if ((! P_RIGHTMOST(opaque)) && - coff[i - 1] == PageGetMaxOffsetNumber(page)) /* yes */ + if ((!P_RIGHTMOST(opaque)) && + coff[i - 1] == PageGetMaxOffsetNumber(page)) /* yes */ { newbuf = _bt_getbuf(rel, opaque->btpo_next, BT_WRITE); newpage = BufferGetPage(newbuf); newopaque = (BTPageOpaque) PageGetSpecialPointer(newpage); coff[i] = _bt_getoff(newpage, cblkno[i]); - if (coff[i] != InvalidOffsetNumber) /* found ! */ + if (coff[i] != InvalidOffsetNumber) /* found ! */ { if (coff[i] != P_FIRSTDATAKEY(newopaque)) elog(ERROR, "bt_fixlevel[%s]: invalid item order(3) (need to recreate index)", RelationGetRelationName(rel)); @@ -1673,7 +1695,7 @@ _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) } /* insert pointer */ ritem = (BTItem) PageGetItem(cpage[i - 1], - PageGetItemId(cpage[i - 1], P_HIKEY)); + PageGetItemId(cpage[i - 1], P_HIKEY)); btitem = _bt_formitem(&(ritem->bti_itup)); ItemPointerSet(&(btitem->bti_itup.t_tid), cblkno[i], P_HIKEY); itemsz = IndexTupleDSize(btitem->bti_itup) @@ -1684,16 +1706,16 @@ _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) if (PageGetFreeSpace(page) < itemsz) { - OffsetNumber firstright; - OffsetNumber itup_off; - BlockNumber itup_blkno; - bool newitemonleft; + OffsetNumber firstright; + OffsetNumber itup_off; + BlockNumber itup_blkno; + bool newitemonleft; firstright = _bt_findsplitloc(rel, page, - newitemoff, itemsz, &newitemonleft); + newitemoff, itemsz, &newitemonleft); newbuf = _bt_split(rel, buf, firstright, - newitemoff, itemsz, btitem, newitemonleft, - &itup_off, &itup_blkno); + newitemoff, itemsz, btitem, newitemonleft, + &itup_off, &itup_blkno); /* what buffer we need in ? */ if (newitemonleft) _bt_relbuf(rel, newbuf, BT_WRITE); @@ -1720,7 +1742,7 @@ _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) /* copy page with pointer to cblkno[cidx] to temp storage */ memmove(tbuf, page, PageGetPageSize(page)); _bt_relbuf(rel, buf, BT_WRITE); - page = (Page)tbuf; + page = (Page) tbuf; opaque = (BTPageOpaque) PageGetSpecialPointer(page); } @@ -1760,18 +1782,19 @@ _bt_fixlevel(Relation rel, Buffer buf, BlockNumber limit) * but it doesn't guarantee full consistency of tree.) */ static void -_bt_fixbranch(Relation rel, BlockNumber lblkno, - BlockNumber rblkno, BTStack true_stack) +_bt_fixbranch(Relation rel, BlockNumber lblkno, + BlockNumber rblkno, BTStack true_stack) { - BlockNumber blkno = true_stack->bts_blkno; - BTStackData stack; - BTPageOpaque opaque; - Buffer buf, rbuf; - Page page; - OffsetNumber offnum; + BlockNumber blkno = true_stack->bts_blkno; + BTStackData stack; + BTPageOpaque opaque; + Buffer buf, + rbuf; + Page page; + OffsetNumber offnum; true_stack = true_stack->bts_parent; - for ( ; ; ) + for (;;) { buf = _bt_getbuf(rel, blkno, BT_READ); @@ -1779,8 +1802,8 @@ _bt_fixbranch(Relation rel, BlockNumber lblkno, _bt_fixlevel(rel, buf, rblkno); /* - * Here parent level should have pointers for both - * lblkno and rblkno and we have to find them. + * Here parent level should have pointers for both lblkno and + * rblkno and we have to find them. */ stack.bts_parent = NULL; stack.bts_blkno = blkno; @@ -1792,7 +1815,7 @@ _bt_fixbranch(Relation rel, BlockNumber lblkno, page = BufferGetPage(buf); offnum = _bt_getoff(page, rblkno); - if (offnum != InvalidOffsetNumber) /* right pointer found */ + if (offnum != InvalidOffsetNumber) /* right pointer found */ { if (offnum <= stack.bts_offset) elog(ERROR, "bt_fixbranch[%s]: invalid item order (need to recreate index)", RelationGetRelationName(rel)); @@ -1829,10 +1852,10 @@ _bt_fixbranch(Relation rel, BlockNumber lblkno, } /* - * Well, we are on the level that was root or unexistent when - * we started traversing tree down. If btpo_parent is updated - * then we'll use it to continue, else we'll fix/restore upper - * levels entirely. + * Well, we are on the level that was root or unexistent when we + * started traversing tree down. If btpo_parent is updated then + * we'll use it to continue, else we'll fix/restore upper levels + * entirely. */ if (!BTreeInvalidParent(opaque)) { @@ -1874,18 +1897,18 @@ _bt_fixbranch(Relation rel, BlockNumber lblkno, static void _bt_fixup(Relation rel, Buffer buf) { - Page page; - BTPageOpaque opaque; - BlockNumber blkno; + Page page; + BTPageOpaque opaque; + BlockNumber blkno; - for ( ; ; ) + for (;;) { page = BufferGetPage(buf); opaque = (BTPageOpaque) PageGetSpecialPointer(page); + /* - * If someone else already created parent pages - * then it's time for _bt_fixtree() to check upper - * levels and fix them, if required. + * If someone else already created parent pages then it's time for + * _bt_fixtree() to check upper levels and fix them, if required. */ if (!BTreeInvalidParent(opaque)) { @@ -1904,13 +1927,12 @@ _bt_fixup(Relation rel, Buffer buf) } /* - * Ok, we are on the leftmost page, it's write locked - * by us and its btpo_parent points to meta page - time - * for _bt_fixroot(). + * Ok, we are on the leftmost page, it's write locked by us and its + * btpo_parent points to meta page - time for _bt_fixroot(). */ elog(NOTICE, "bt_fixup[%s]: fixing root page", RelationGetRelationName(rel)); - buf = _bt_fixroot(rel, buf, true); - _bt_relbuf(rel, buf, BT_WRITE); + buf = _bt_fixroot(rel, buf, true); + _bt_relbuf(rel, buf, BT_WRITE); return; } @@ -1918,23 +1940,23 @@ _bt_fixup(Relation rel, Buffer buf) static OffsetNumber _bt_getoff(Page page, BlockNumber blkno) { - BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page); - OffsetNumber maxoff = PageGetMaxOffsetNumber(page); - OffsetNumber offnum = P_FIRSTDATAKEY(opaque); - BlockNumber curblkno; - ItemId itemid; - BTItem item; - - for ( ; offnum <= maxoff; offnum++) + BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page); + OffsetNumber maxoff = PageGetMaxOffsetNumber(page); + OffsetNumber offnum = P_FIRSTDATAKEY(opaque); + BlockNumber curblkno; + ItemId itemid; + BTItem item; + + for (; offnum <= maxoff; offnum++) { itemid = PageGetItemId(page, offnum); item = (BTItem) PageGetItem(page, itemid); curblkno = ItemPointerGetBlockNumber(&(item->bti_itup.t_tid)); if (curblkno == blkno) - return(offnum); + return (offnum); } - return(InvalidOffsetNumber); + return (InvalidOffsetNumber); } /* @@ -1961,9 +1983,9 @@ _bt_pgaddtup(Relation rel, const char *where) { BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page); - BTItemData truncitem; + BTItemData truncitem; - if (! P_ISLEAF(opaque) && itup_off == P_FIRSTDATAKEY(opaque)) + if (!P_ISLEAF(opaque) && itup_off == P_FIRSTDATAKEY(opaque)) { memcpy(&truncitem, btitem, sizeof(BTItemData)); truncitem.bti_itup.t_info = sizeof(BTItemData); diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c index 4c854fe7913..460d6c834c1 100644 --- a/src/backend/access/nbtree/nbtpage.c +++ b/src/backend/access/nbtree/nbtpage.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtpage.c,v 1.50 2001/02/07 23:35:33 vadim Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtpage.c,v 1.51 2001/03/22 03:59:14 momjian Exp $ * * NOTES * Postgres btree pages look like ordinary relation pages. The opaque @@ -28,7 +28,7 @@ #include "miscadmin.h" #include "storage/lmgr.h" -extern bool FixBTree; /* comments in nbtree.c */ +extern bool FixBTree; /* comments in nbtree.c */ extern Buffer _bt_fixroot(Relation rel, Buffer oldrootbuf, bool release); /* @@ -100,7 +100,7 @@ _bt_metapinit(Relation rel) * * The access type parameter (BT_READ or BT_WRITE) controls whether * a new root page will be created or not. If access = BT_READ, - * and no root page exists, we just return InvalidBuffer. For + * and no root page exists, we just return InvalidBuffer. For * BT_WRITE, we try to create the root page if it doesn't exist. * NOTE that the returned root page will have only a read lock set * on it even if access = BT_WRITE! @@ -178,20 +178,20 @@ _bt_getroot(Relation rel, int access) /* XLOG stuff */ { - xl_btree_newroot xlrec; - XLogRecPtr recptr; - XLogRecData rdata; + xl_btree_newroot xlrec; + XLogRecPtr recptr; + XLogRecData rdata; xlrec.node = rel->rd_node; xlrec.level = 1; BlockIdSet(&(xlrec.rootblk), rootblkno); rdata.buffer = InvalidBuffer; - rdata.data = (char*)&xlrec; + rdata.data = (char *) &xlrec; rdata.len = SizeOfBtreeNewroot; rdata.next = NULL; recptr = XLogInsert(RM_BTREE_ID, - XLOG_BTREE_NEWROOT|XLOG_BTREE_LEAF, &rdata); + XLOG_BTREE_NEWROOT | XLOG_BTREE_LEAF, &rdata); PageSetLSN(rootpage, recptr); PageSetSUI(rootpage, ThisStartUpID); @@ -212,6 +212,7 @@ _bt_getroot(Relation rel, int access) } else { + /* * Metadata initialized by someone else. In order to * guarantee no deadlocks, we have to release the metadata @@ -232,30 +233,31 @@ _bt_getroot(Relation rel, int access) /* * Race condition: If the root page split between the time we looked * at the metadata page and got the root buffer, then we got the wrong - * buffer. Release it and try again. + * buffer. Release it and try again. */ rootpage = BufferGetPage(rootbuf); rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpage); - if (! P_ISROOT(rootopaque)) + if (!P_ISROOT(rootopaque)) { + /* - * It happened, but if root page splitter failed to create - * new root page then we'll go in loop trying to call - * _bt_getroot again and again. + * It happened, but if root page splitter failed to create new + * root page then we'll go in loop trying to call _bt_getroot + * again and again. */ if (FixBTree) { - Buffer newrootbuf; + Buffer newrootbuf; -check_parent:; - if (BTreeInvalidParent(rootopaque)) /* unupdated! */ + check_parent:; + if (BTreeInvalidParent(rootopaque)) /* unupdated! */ { LockBuffer(rootbuf, BUFFER_LOCK_UNLOCK); LockBuffer(rootbuf, BT_WRITE); /* handle concurrent fix of root page */ - if (BTreeInvalidParent(rootopaque)) /* unupdated! */ + if (BTreeInvalidParent(rootopaque)) /* unupdated! */ { elog(NOTICE, "bt_getroot[%s]: fixing root page", RelationGetRelationName(rel)); newrootbuf = _bt_fixroot(rel, rootbuf, true); @@ -266,20 +268,22 @@ check_parent:; rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpage); /* New root might be splitted while changing lock */ if (P_ISROOT(rootopaque)) - return(rootbuf); + return (rootbuf); /* rootbuf is read locked */ goto check_parent; } - else /* someone else already fixed root */ + else +/* someone else already fixed root */ { LockBuffer(rootbuf, BUFFER_LOCK_UNLOCK); LockBuffer(rootbuf, BT_READ); } } + /* - * Ok, here we have old root page with btpo_parent pointing - * to upper level - check parent page because of there is - * good chance that parent is root page. + * Ok, here we have old root page with btpo_parent pointing to + * upper level - check parent page because of there is good + * chance that parent is root page. */ newrootbuf = _bt_getbuf(rel, rootopaque->btpo_parent, BT_READ); _bt_relbuf(rel, rootbuf, BT_READ); @@ -287,7 +291,7 @@ check_parent:; rootpage = BufferGetPage(rootbuf); rootopaque = (BTPageOpaque) PageGetSpecialPointer(rootpage); if (P_ISROOT(rootopaque)) - return(rootbuf); + return (rootbuf); /* no luck -:( */ } @@ -366,7 +370,7 @@ _bt_relbuf(Relation rel, Buffer buf, int access) * and a pin on the buffer. * * NOTE: actually, the buffer manager just marks the shared buffer page - * dirty here, the real I/O happens later. Since we can't persuade the + * dirty here, the real I/O happens later. Since we can't persuade the * Unix kernel to schedule disk writes in a particular order, there's not * much point in worrying about this. The most we can say is that all the * writes will occur before commit. @@ -468,14 +472,14 @@ _bt_pagedel(Relation rel, ItemPointer tid) PageIndexTupleDelete(page, offno); /* XLOG stuff */ { - xl_btree_delete xlrec; - XLogRecPtr recptr; - XLogRecData rdata[2]; + xl_btree_delete xlrec; + XLogRecPtr recptr; + XLogRecData rdata[2]; xlrec.target.node = rel->rd_node; xlrec.target.tid = *tid; rdata[0].buffer = InvalidBuffer; - rdata[0].data = (char*)&xlrec; + rdata[0].data = (char *) &xlrec; rdata[0].len = SizeOfBtreeDelete; rdata[0].next = &(rdata[1]); diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c index f02dfcbd128..97d99da4fde 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -12,7 +12,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.78 2001/02/07 23:35:33 vadim Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtree.c,v 1.79 2001/03/22 03:59:15 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -30,7 +30,8 @@ bool BuildingBtree = false; /* see comment in btbuild() */ bool FastBuild = true; /* use sort/build instead */ - /* of insertion build */ + + /* of insertion build */ /* @@ -52,12 +53,14 @@ static void _bt_restscan(IndexScanDesc scan); Datum btbuild(PG_FUNCTION_ARGS) { - Relation heap = (Relation) PG_GETARG_POINTER(0); - Relation index = (Relation) PG_GETARG_POINTER(1); - IndexInfo *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2); - Node *oldPred = (Node *) PG_GETARG_POINTER(3); + Relation heap = (Relation) PG_GETARG_POINTER(0); + Relation index = (Relation) PG_GETARG_POINTER(1); + IndexInfo *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2); + Node *oldPred = (Node *) PG_GETARG_POINTER(3); + #ifdef NOT_USED - IndexStrategy istrat = (IndexStrategy) PG_GETARG_POINTER(4); + IndexStrategy istrat = (IndexStrategy) PG_GETARG_POINTER(4); + #endif HeapScanDesc hscan; HeapTuple htup; @@ -69,9 +72,11 @@ btbuild(PG_FUNCTION_ARGS) int nhtups, nitups; Node *pred = indexInfo->ii_Predicate; + #ifndef OMIT_PARTIAL_INDEX TupleTable tupleTable; TupleTableSlot *slot; + #endif ExprContext *econtext; InsertIndexResult res = NULL; @@ -79,15 +84,16 @@ btbuild(PG_FUNCTION_ARGS) BTItem btitem; bool usefast; Snapshot snapshot; - TransactionId XmaxRecent; + TransactionId XmaxRecent; + /* - * spool2 is needed only when the index is an unique index. - * Dead tuples are put into spool2 instead of spool in - * order to avoid uniqueness check. + * spool2 is needed only when the index is an unique index. Dead + * tuples are put into spool2 instead of spool in order to avoid + * uniqueness check. */ - BTSpool *spool2 = NULL; + BTSpool *spool2 = NULL; bool tupleIsAlive; - int dead_count; + int dead_count; /* note that this is a new btree */ BuildingBtree = true; @@ -103,7 +109,7 @@ btbuild(PG_FUNCTION_ARGS) #ifdef BTREE_BUILD_STATS if (Show_btree_build_stats) ResetUsage(); -#endif /* BTREE_BUILD_STATS */ +#endif /* BTREE_BUILD_STATS */ /* initialize the btree index metadata page (if this is a new index) */ if (oldPred == NULL) @@ -155,10 +161,10 @@ btbuild(PG_FUNCTION_ARGS) if (usefast) { spool = _bt_spoolinit(index, indexInfo->ii_Unique); + /* - * Different from spool,the uniqueness isn't checked - * for spool2. - */ + * Different from spool,the uniqueness isn't checked for spool2. + */ if (indexInfo->ii_Unique) spool2 = _bt_spoolinit(index, false); } @@ -187,12 +193,13 @@ btbuild(PG_FUNCTION_ARGS) } else tupleIsAlive = true; - + MemoryContextReset(econtext->ecxt_per_tuple_memory); nhtups++; #ifndef OMIT_PARTIAL_INDEX + /* * If oldPred != NULL, this is an EXTEND INDEX command, so skip * this tuple if it was already in the existing partial index @@ -253,8 +260,7 @@ btbuild(PG_FUNCTION_ARGS) * btree pages - NULLs greater NOT_NULLs and NULL = NULL is TRUE. * Sure, it's just rule for placing/finding items and no more - * keytest'll return FALSE for a = 5 for items having 'a' isNULL. - * Look at _bt_compare for how it works. - * - vadim 03/23/97 + * Look at _bt_compare for how it works. - vadim 03/23/97 * * if (itup->t_info & INDEX_NULL_MASK) { pfree(itup); continue; } */ @@ -271,7 +277,8 @@ btbuild(PG_FUNCTION_ARGS) { if (tupleIsAlive || !spool2) _bt_spool(btitem, spool); - else /* dead tuples are put into spool2 */ + else +/* dead tuples are put into spool2 */ { dead_count++; _bt_spool(btitem, spool2); @@ -288,7 +295,7 @@ btbuild(PG_FUNCTION_ARGS) /* okay, all heap tuples are indexed */ heap_endscan(hscan); - if (spool2 && !dead_count) /* spool2 was found to be unnecessary */ + if (spool2 && !dead_count) /* spool2 was found to be unnecessary */ { _bt_spooldestroy(spool2); spool2 = NULL; @@ -296,9 +303,7 @@ btbuild(PG_FUNCTION_ARGS) #ifndef OMIT_PARTIAL_INDEX if (pred != NULL || oldPred != NULL) - { ExecDropTupleTable(tupleTable, true); - } #endif /* OMIT_PARTIAL_INDEX */ FreeExprContext(econtext); @@ -322,7 +327,7 @@ btbuild(PG_FUNCTION_ARGS) ShowUsage(); ResetUsage(); } -#endif /* BTREE_BUILD_STATS */ +#endif /* BTREE_BUILD_STATS */ /* * Since we just counted the tuples in the heap, we update its stats @@ -368,11 +373,11 @@ btbuild(PG_FUNCTION_ARGS) Datum btinsert(PG_FUNCTION_ARGS) { - Relation rel = (Relation) PG_GETARG_POINTER(0); - Datum *datum = (Datum *) PG_GETARG_POINTER(1); - char *nulls = (char *) PG_GETARG_POINTER(2); - ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3); - Relation heapRel = (Relation) PG_GETARG_POINTER(4); + Relation rel = (Relation) PG_GETARG_POINTER(0); + Datum *datum = (Datum *) PG_GETARG_POINTER(1); + char *nulls = (char *) PG_GETARG_POINTER(2); + ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3); + Relation heapRel = (Relation) PG_GETARG_POINTER(4); InsertIndexResult res; BTItem btitem; IndexTuple itup; @@ -396,8 +401,8 @@ btinsert(PG_FUNCTION_ARGS) Datum btgettuple(PG_FUNCTION_ARGS) { - IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); - ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1); + IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); + ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1); RetrieveIndexResult res; /* @@ -408,10 +413,11 @@ btgettuple(PG_FUNCTION_ARGS) if (ItemPointerIsValid(&(scan->currentItemData))) { + /* * Restore scan position using heap TID returned by previous call - * to btgettuple(). _bt_restscan() re-grabs the read lock on - * the buffer, too. + * to btgettuple(). _bt_restscan() re-grabs the read lock on the + * buffer, too. */ _bt_restscan(scan); res = _bt_next(scan, dir); @@ -421,8 +427,8 @@ btgettuple(PG_FUNCTION_ARGS) /* * Save heap TID to use it in _bt_restscan. Then release the read - * lock on the buffer so that we aren't blocking other backends. - * NOTE: we do keep the pin on the buffer! + * lock on the buffer so that we aren't blocking other backends. NOTE: + * we do keep the pin on the buffer! */ if (res) { @@ -461,11 +467,13 @@ btbeginscan(PG_FUNCTION_ARGS) Datum btrescan(PG_FUNCTION_ARGS) { - IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); + IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); + #ifdef NOT_USED /* XXX surely it's wrong to ignore this? */ - bool fromEnd = PG_GETARG_BOOL(1); + bool fromEnd = PG_GETARG_BOOL(1); + #endif - ScanKey scankey = (ScanKey) PG_GETARG_POINTER(2); + ScanKey scankey = (ScanKey) PG_GETARG_POINTER(2); ItemPointer iptr; BTScanOpaque so; @@ -540,7 +548,7 @@ btmovescan(IndexScanDesc scan, Datum v) Datum btendscan(PG_FUNCTION_ARGS) { - IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); + IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ItemPointer iptr; BTScanOpaque so; @@ -578,7 +586,7 @@ btendscan(PG_FUNCTION_ARGS) Datum btmarkpos(PG_FUNCTION_ARGS) { - IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); + IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ItemPointer iptr; BTScanOpaque so; @@ -610,7 +618,7 @@ btmarkpos(PG_FUNCTION_ARGS) Datum btrestrpos(PG_FUNCTION_ARGS) { - IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); + IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0); ItemPointer iptr; BTScanOpaque so; @@ -640,8 +648,8 @@ btrestrpos(PG_FUNCTION_ARGS) Datum btdelete(PG_FUNCTION_ARGS) { - Relation rel = (Relation) PG_GETARG_POINTER(0); - ItemPointer tid = (ItemPointer) PG_GETARG_POINTER(1); + Relation rel = (Relation) PG_GETARG_POINTER(0); + ItemPointer tid = (ItemPointer) PG_GETARG_POINTER(1); /* adjust any active scans that will be affected by this deletion */ _bt_adjscans(rel, tid); @@ -671,8 +679,8 @@ _bt_restscan(IndexScanDesc scan) BlockNumber blkno; /* - * Get back the read lock we were holding on the buffer. - * (We still have a reference-count pin on it, though.) + * Get back the read lock we were holding on the buffer. (We still + * have a reference-count pin on it, though.) */ LockBuffer(buf, BT_READ); @@ -689,13 +697,13 @@ _bt_restscan(IndexScanDesc scan) if (!ItemPointerIsValid(&target)) { ItemPointerSetOffsetNumber(current, - OffsetNumberPrev(P_FIRSTDATAKEY(opaque))); + OffsetNumberPrev(P_FIRSTDATAKEY(opaque))); return; } /* - * The item we were on may have moved right due to insertions. - * Find it again. + * The item we were on may have moved right due to insertions. Find it + * again. */ for (;;) { @@ -717,7 +725,8 @@ _bt_restscan(IndexScanDesc scan) } /* - * By here, the item we're looking for moved right at least one page + * By here, the item we're looking for moved right at least one + * page */ if (P_RIGHTMOST(opaque)) elog(FATAL, "_bt_restscan: my bits moved right off the end of the world!" @@ -742,14 +751,14 @@ _bt_restore_page(Page page, char *from, int len) Size itemsz; char *end = from + len; - for ( ; from < end; ) + for (; from < end;) { memcpy(&btdata, from, sizeof(BTItemData)); itemsz = IndexTupleDSize(btdata.bti_itup) + - (sizeof(BTItemData) - sizeof(IndexTupleData)); + (sizeof(BTItemData) - sizeof(IndexTupleData)); itemsz = MAXALIGN(itemsz); if (PageAddItem(page, (Item) from, itemsz, - FirstOffsetNumber, LP_USED) == InvalidOffsetNumber) + FirstOffsetNumber, LP_USED) == InvalidOffsetNumber) elog(STOP, "_bt_restore_page: can't add item to page"); from += itemsz; } @@ -758,20 +767,20 @@ _bt_restore_page(Page page, char *from, int len) static void btree_xlog_delete(bool redo, XLogRecPtr lsn, XLogRecord *record) { - xl_btree_delete *xlrec; - Relation reln; - Buffer buffer; - Page page; + xl_btree_delete *xlrec; + Relation reln; + Buffer buffer; + Page page; if (!redo || (record->xl_info & XLR_BKP_BLOCK_1)) return; - xlrec = (xl_btree_delete*) XLogRecGetData(record); + xlrec = (xl_btree_delete *) XLogRecGetData(record); reln = XLogOpenRelation(redo, RM_BTREE_ID, xlrec->target.node); if (!RelationIsValid(reln)) return; - buffer = XLogReadBuffer(false, reln, - ItemPointerGetBlockNumber(&(xlrec->target.tid))); + buffer = XLogReadBuffer(false, reln, + ItemPointerGetBlockNumber(&(xlrec->target.tid))); if (!BufferIsValid(buffer)) elog(STOP, "btree_delete_redo: block unfound"); page = (Page) BufferGetPage(buffer); @@ -796,21 +805,21 @@ btree_xlog_delete(bool redo, XLogRecPtr lsn, XLogRecord *record) static void btree_xlog_insert(bool redo, XLogRecPtr lsn, XLogRecord *record) { - xl_btree_insert *xlrec; - Relation reln; - Buffer buffer; - Page page; - BTPageOpaque pageop; + xl_btree_insert *xlrec; + Relation reln; + Buffer buffer; + Page page; + BTPageOpaque pageop; if (redo && (record->xl_info & XLR_BKP_BLOCK_1)) return; - xlrec = (xl_btree_insert*) XLogRecGetData(record); + xlrec = (xl_btree_insert *) XLogRecGetData(record); reln = XLogOpenRelation(redo, RM_BTREE_ID, xlrec->target.node); if (!RelationIsValid(reln)) return; - buffer = XLogReadBuffer(false, reln, - ItemPointerGetBlockNumber(&(xlrec->target.tid))); + buffer = XLogReadBuffer(false, reln, + ItemPointerGetBlockNumber(&(xlrec->target.tid))); if (!BufferIsValid(buffer)) elog(STOP, "btree_insert_%sdo: block unfound", (redo) ? "re" : "un"); page = (Page) BufferGetPage(buffer); @@ -825,11 +834,11 @@ btree_xlog_insert(bool redo, XLogRecPtr lsn, XLogRecord *record) UnlockAndReleaseBuffer(buffer); return; } - if (PageAddItem(page, (Item)((char*)xlrec + SizeOfBtreeInsert), - record->xl_len - SizeOfBtreeInsert, - ItemPointerGetOffsetNumber(&(xlrec->target.tid)), - LP_USED) == InvalidOffsetNumber) - elog(STOP, "btree_insert_redo: failed to add item"); + if (PageAddItem(page, (Item) ((char *) xlrec + SizeOfBtreeInsert), + record->xl_len - SizeOfBtreeInsert, + ItemPointerGetOffsetNumber(&(xlrec->target.tid)), + LP_USED) == InvalidOffsetNumber) + elog(STOP, "btree_insert_redo: failed to add item"); PageSetLSN(page, lsn); PageSetSUI(page, ThisStartUpID); @@ -840,7 +849,7 @@ btree_xlog_insert(bool redo, XLogRecPtr lsn, XLogRecord *record) if (XLByteLT(PageGetLSN(page), lsn)) elog(STOP, "btree_insert_undo: bad page LSN"); - if (! P_ISLEAF(pageop)) + if (!P_ISLEAF(pageop)) { UnlockAndReleaseBuffer(buffer); return; @@ -855,14 +864,14 @@ btree_xlog_insert(bool redo, XLogRecPtr lsn, XLogRecord *record) static void btree_xlog_split(bool redo, bool onleft, XLogRecPtr lsn, XLogRecord *record) { - xl_btree_split *xlrec = (xl_btree_split*) XLogRecGetData(record); - Relation reln; - BlockNumber blkno; - Buffer buffer; - Page page; - BTPageOpaque pageop; - char *op = (redo) ? "redo" : "undo"; - bool isleaf = (record->xl_info & XLOG_BTREE_LEAF); + xl_btree_split *xlrec = (xl_btree_split *) XLogRecGetData(record); + Relation reln; + BlockNumber blkno; + Buffer buffer; + Page page; + BTPageOpaque pageop; + char *op = (redo) ? "redo" : "undo"; + bool isleaf = (record->xl_info & XLOG_BTREE_LEAF); reln = XLogOpenRelation(redo, RM_BTREE_ID, xlrec->target.node); if (!RelationIsValid(reln)) @@ -870,7 +879,7 @@ btree_xlog_split(bool redo, bool onleft, XLogRecPtr lsn, XLogRecord *record) /* Left (original) sibling */ blkno = (onleft) ? ItemPointerGetBlockNumber(&(xlrec->target.tid)) : - BlockIdGetBlockNumber(&(xlrec->otherblk)); + BlockIdGetBlockNumber(&(xlrec->otherblk)); buffer = XLogReadBuffer(false, reln, blkno); if (!BufferIsValid(buffer)) elog(STOP, "btree_split_%s: lost left sibling", op); @@ -892,13 +901,14 @@ btree_xlog_split(bool redo, bool onleft, XLogRecPtr lsn, XLogRecord *record) pageop->btpo_next = ItemPointerGetBlockNumber(&(xlrec->target.tid)); pageop->btpo_flags = (isleaf) ? BTP_LEAF : 0; - _bt_restore_page(page, (char*)xlrec + SizeOfBtreeSplit, xlrec->leftlen); + _bt_restore_page(page, (char *) xlrec + SizeOfBtreeSplit, xlrec->leftlen); PageSetLSN(page, lsn); PageSetSUI(page, ThisStartUpID); UnlockAndWriteBuffer(buffer); } - else /* undo */ + else +/* undo */ { if (XLByteLT(PageGetLSN(page), lsn)) elog(STOP, "btree_split_undo: bad left sibling LSN"); @@ -906,8 +916,8 @@ btree_xlog_split(bool redo, bool onleft, XLogRecPtr lsn, XLogRecord *record) } /* Right (new) sibling */ - blkno = (onleft) ? BlockIdGetBlockNumber(&(xlrec->otherblk)) : - ItemPointerGetBlockNumber(&(xlrec->target.tid)); + blkno = (onleft) ? BlockIdGetBlockNumber(&(xlrec->otherblk)) : + ItemPointerGetBlockNumber(&(xlrec->target.tid)); buffer = XLogReadBuffer((redo) ? true : false, reln, blkno); if (!BufferIsValid(buffer)) elog(STOP, "btree_split_%s: lost right sibling", op); @@ -922,21 +932,22 @@ btree_xlog_split(bool redo, bool onleft, XLogRecPtr lsn, XLogRecord *record) if (redo) { pageop->btpo_parent = BlockIdGetBlockNumber(&(xlrec->parentblk)); - pageop->btpo_prev = (onleft) ? - ItemPointerGetBlockNumber(&(xlrec->target.tid)) : - BlockIdGetBlockNumber(&(xlrec->otherblk)); + pageop->btpo_prev = (onleft) ? + ItemPointerGetBlockNumber(&(xlrec->target.tid)) : + BlockIdGetBlockNumber(&(xlrec->otherblk)); pageop->btpo_next = BlockIdGetBlockNumber(&(xlrec->rightblk)); pageop->btpo_flags = (isleaf) ? BTP_LEAF : 0; _bt_restore_page(page, - (char*)xlrec + SizeOfBtreeSplit + xlrec->leftlen, - record->xl_len - SizeOfBtreeSplit - xlrec->leftlen); + (char *) xlrec + SizeOfBtreeSplit + xlrec->leftlen, + record->xl_len - SizeOfBtreeSplit - xlrec->leftlen); PageSetLSN(page, lsn); PageSetSUI(page, ThisStartUpID); UnlockAndWriteBuffer(buffer); } - else /* undo */ + else +/* undo */ { if (XLByteLT(PageGetLSN(page), lsn)) elog(STOP, "btree_split_undo: bad right sibling LSN"); @@ -965,9 +976,9 @@ btree_xlog_split(bool redo, bool onleft, XLogRecPtr lsn, XLogRecord *record) return; } pageop = (BTPageOpaque) PageGetSpecialPointer(page); - pageop->btpo_prev = (onleft) ? - BlockIdGetBlockNumber(&(xlrec->otherblk)) : - ItemPointerGetBlockNumber(&(xlrec->target.tid)); + pageop->btpo_prev = (onleft) ? + BlockIdGetBlockNumber(&(xlrec->otherblk)) : + ItemPointerGetBlockNumber(&(xlrec->target.tid)); PageSetLSN(page, lsn); PageSetSUI(page, ThisStartUpID); @@ -977,14 +988,14 @@ btree_xlog_split(bool redo, bool onleft, XLogRecPtr lsn, XLogRecord *record) static void btree_xlog_newroot(bool redo, XLogRecPtr lsn, XLogRecord *record) { - xl_btree_newroot *xlrec = (xl_btree_newroot*) XLogRecGetData(record); - Relation reln; - Buffer buffer; - Page page; - BTPageOpaque pageop; - Buffer metabuf; - Page metapg; - BTMetaPageData md; + xl_btree_newroot *xlrec = (xl_btree_newroot *) XLogRecGetData(record); + Relation reln; + Buffer buffer; + Page page; + BTPageOpaque pageop; + Buffer metabuf; + Page metapg; + BTMetaPageData md; if (!redo) return; @@ -1011,8 +1022,8 @@ btree_xlog_newroot(bool redo, XLogRecPtr lsn, XLogRecord *record) if (record->xl_len > SizeOfBtreeNewroot) _bt_restore_page(page, - (char*)xlrec + SizeOfBtreeNewroot, - record->xl_len - SizeOfBtreeNewroot); + (char *) xlrec + SizeOfBtreeNewroot, + record->xl_len - SizeOfBtreeNewroot); PageSetLSN(page, lsn); PageSetSUI(page, ThisStartUpID); @@ -1037,7 +1048,7 @@ btree_xlog_newroot(bool redo, XLogRecPtr lsn, XLogRecord *record) void btree_redo(XLogRecPtr lsn, XLogRecord *record) { - uint8 info = record->xl_info & ~XLR_INFO_MASK; + uint8 info = record->xl_info & ~XLR_INFO_MASK; info &= ~XLOG_BTREE_LEAF; if (info == XLOG_BTREE_DELETE) @@ -1045,9 +1056,9 @@ btree_redo(XLogRecPtr lsn, XLogRecord *record) else if (info == XLOG_BTREE_INSERT) btree_xlog_insert(true, lsn, record); else if (info == XLOG_BTREE_SPLIT) - btree_xlog_split(true, false, lsn, record); /* new item on the right */ + btree_xlog_split(true, false, lsn, record); /* new item on the right */ else if (info == XLOG_BTREE_SPLEFT) - btree_xlog_split(true, true, lsn, record); /* new item on the left */ + btree_xlog_split(true, true, lsn, record); /* new item on the left */ else if (info == XLOG_BTREE_NEWROOT) btree_xlog_newroot(true, lsn, record); else @@ -1057,7 +1068,7 @@ btree_redo(XLogRecPtr lsn, XLogRecord *record) void btree_undo(XLogRecPtr lsn, XLogRecord *record) { - uint8 info = record->xl_info & ~XLR_INFO_MASK; + uint8 info = record->xl_info & ~XLR_INFO_MASK; info &= ~XLOG_BTREE_LEAF; if (info == XLOG_BTREE_DELETE) @@ -1065,9 +1076,9 @@ btree_undo(XLogRecPtr lsn, XLogRecord *record) else if (info == XLOG_BTREE_INSERT) btree_xlog_insert(false, lsn, record); else if (info == XLOG_BTREE_SPLIT) - btree_xlog_split(false, false, lsn, record);/* new item on the right */ + btree_xlog_split(false, false, lsn, record); /* new item on the right */ else if (info == XLOG_BTREE_SPLEFT) - btree_xlog_split(false, true, lsn, record); /* new item on the left */ + btree_xlog_split(false, true, lsn, record); /* new item on the left */ else if (info == XLOG_BTREE_NEWROOT) btree_xlog_newroot(false, lsn, record); else @@ -1078,45 +1089,49 @@ static void out_target(char *buf, xl_btreetid *target) { sprintf(buf + strlen(buf), "node %u/%u; tid %u/%u", - target->node.tblNode, target->node.relNode, - ItemPointerGetBlockNumber(&(target->tid)), - ItemPointerGetOffsetNumber(&(target->tid))); + target->node.tblNode, target->node.relNode, + ItemPointerGetBlockNumber(&(target->tid)), + ItemPointerGetOffsetNumber(&(target->tid))); } - + void -btree_desc(char *buf, uint8 xl_info, char* rec) +btree_desc(char *buf, uint8 xl_info, char *rec) { - uint8 info = xl_info & ~XLR_INFO_MASK; + uint8 info = xl_info & ~XLR_INFO_MASK; info &= ~XLOG_BTREE_LEAF; if (info == XLOG_BTREE_INSERT) { - xl_btree_insert *xlrec = (xl_btree_insert*) rec; + xl_btree_insert *xlrec = (xl_btree_insert *) rec; + strcat(buf, "insert: "); out_target(buf, &(xlrec->target)); } else if (info == XLOG_BTREE_DELETE) { - xl_btree_delete *xlrec = (xl_btree_delete*) rec; + xl_btree_delete *xlrec = (xl_btree_delete *) rec; + strcat(buf, "delete: "); out_target(buf, &(xlrec->target)); } else if (info == XLOG_BTREE_SPLIT || info == XLOG_BTREE_SPLEFT) { - xl_btree_split *xlrec = (xl_btree_split*) rec; - sprintf(buf + strlen(buf), "split(%s): ", - (info == XLOG_BTREE_SPLIT) ? "right" : "left"); + xl_btree_split *xlrec = (xl_btree_split *) rec; + + sprintf(buf + strlen(buf), "split(%s): ", + (info == XLOG_BTREE_SPLIT) ? "right" : "left"); out_target(buf, &(xlrec->target)); sprintf(buf + strlen(buf), "; oth %u; rgh %u", - BlockIdGetBlockNumber(&xlrec->otherblk), - BlockIdGetBlockNumber(&xlrec->rightblk)); + BlockIdGetBlockNumber(&xlrec->otherblk), + BlockIdGetBlockNumber(&xlrec->rightblk)); } else if (info == XLOG_BTREE_NEWROOT) { - xl_btree_newroot *xlrec = (xl_btree_newroot*) rec; + xl_btree_newroot *xlrec = (xl_btree_newroot *) rec; + sprintf(buf + strlen(buf), "root: node %u/%u; blk %u", - xlrec->node.tblNode, xlrec->node.relNode, - BlockIdGetBlockNumber(&xlrec->rootblk)); + xlrec->node.tblNode, xlrec->node.relNode, + BlockIdGetBlockNumber(&xlrec->rootblk)); } else strcat(buf, "UNKNOWN"); diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c index 6f41ab9c847..d8b8e0682a0 100644 --- a/src/backend/access/nbtree/nbtsearch.c +++ b/src/backend/access/nbtree/nbtsearch.c @@ -8,7 +8,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.63 2001/01/24 19:42:49 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.64 2001/03/22 03:59:15 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -32,20 +32,20 @@ static RetrieveIndexResult _bt_endpoint(IndexScanDesc scan, ScanDirection dir); * * NOTE that the returned buffer is read-locked regardless of the access * parameter. However, access = BT_WRITE will allow an empty root page - * to be created and returned. When access = BT_READ, an empty index + * to be created and returned. When access = BT_READ, an empty index * will result in *bufP being set to InvalidBuffer. */ BTStack _bt_search(Relation rel, int keysz, ScanKey scankey, Buffer *bufP, int access) { - BTStack stack_in = NULL; + BTStack stack_in = NULL; /* Get the root page to start with */ *bufP = _bt_getroot(rel, access); /* If index is empty and access = BT_READ, no root page is created. */ - if (! BufferIsValid(*bufP)) + if (!BufferIsValid(*bufP)) return (BTStack) NULL; /* Loop iterates once per level descended in the tree */ @@ -79,13 +79,13 @@ _bt_search(Relation rel, int keysz, ScanKey scankey, par_blkno = BufferGetBlockNumber(*bufP); /* - * We need to save the bit image of the index entry we chose in the - * parent page on a stack. In case we split the tree, we'll use this - * bit image to figure out what our real parent page is, in case the - * parent splits while we're working lower in the tree. See the paper - * by Lehman and Yao for how this is detected and handled. (We use the - * child link to disambiguate duplicate keys in the index -- Lehman - * and Yao disallow duplicate keys.) + * We need to save the bit image of the index entry we chose in + * the parent page on a stack. In case we split the tree, we'll + * use this bit image to figure out what our real parent page is, + * in case the parent splits while we're working lower in the + * tree. See the paper by Lehman and Yao for how this is detected + * and handled. (We use the child link to disambiguate duplicate + * keys in the index -- Lehman and Yao disallow duplicate keys.) */ new_stack = (BTStack) palloc(sizeof(BTStackData)); new_stack->bts_blkno = par_blkno; @@ -98,9 +98,9 @@ _bt_search(Relation rel, int keysz, ScanKey scankey, *bufP = _bt_getbuf(rel, blkno, BT_READ); /* - * Race -- the page we just grabbed may have split since we read its - * pointer in the parent. If it has, we may need to move right to its - * new sibling. Do that. + * Race -- the page we just grabbed may have split since we read + * its pointer in the parent. If it has, we may need to move + * right to its new sibling. Do that. */ *bufP = _bt_moveright(rel, *bufP, keysz, scankey, BT_READ); @@ -127,7 +127,7 @@ _bt_search(Relation rel, int keysz, ScanKey scankey, * * On entry, we have the buffer pinned and a lock of the proper type. * If we move right, we release the buffer and lock and acquire the - * same on the right sibling. Return value is the buffer we stop at. + * same on the right sibling. Return value is the buffer we stop at. */ Buffer _bt_moveright(Relation rel, @@ -153,7 +153,7 @@ _bt_moveright(Relation rel, _bt_compare(rel, keysz, scankey, page, P_HIKEY) > 0) { /* step right one page */ - BlockNumber rblkno = opaque->btpo_next; + BlockNumber rblkno = opaque->btpo_next; _bt_relbuf(rel, buf, access); buf = _bt_getbuf(rel, rblkno, access); @@ -184,7 +184,7 @@ _bt_moveright(Relation rel, * find all leaf keys >= given scankey. * * This procedure is not responsible for walking right, it just examines - * the given page. _bt_binsrch() has no lock or refcount side effects + * the given page. _bt_binsrch() has no lock or refcount side effects * on the buffer. */ OffsetNumber @@ -299,7 +299,7 @@ _bt_compare(Relation rel, * Force result ">" if target item is first data item on an internal * page --- see NOTE above. */ - if (! P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque)) + if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque)) return 1; btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum)); @@ -327,7 +327,7 @@ _bt_compare(Relation rel, datum = index_getattr(itup, entry->sk_attno, itupdesc, &isNull); /* see comments about NULLs handling in btbuild */ - if (entry->sk_flags & SK_ISNULL) /* key is NULL */ + if (entry->sk_flags & SK_ISNULL) /* key is NULL */ { if (isNull) result = 0; /* NULL "=" NULL */ @@ -458,10 +458,10 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) _bt_orderkeys(rel, so); /* - * Quit now if _bt_orderkeys() discovered that the scan keys can - * never be satisfied (eg, x == 1 AND x > 2). + * Quit now if _bt_orderkeys() discovered that the scan keys can never + * be satisfied (eg, x == 1 AND x > 2). */ - if (! so->qual_ok) + if (!so->qual_ok) return (RetrieveIndexResult) NULL; /* @@ -484,17 +484,16 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) break; strat = _bt_getstrat(rel, attno, so->keyData[i].sk_procedure); + /* * Can we use this key as a starting boundary for this attr? * - * We can use multiple keys if they look like, say, = >= = - * but we have to stop after accepting a > or < boundary. + * We can use multiple keys if they look like, say, = >= = but we + * have to stop after accepting a > or < boundary. */ if (strat == strat_total || strat == BTEqualStrategyNumber) - { nKeyIs[keysCount++] = i; - } else if (ScanDirectionIsBackward(dir) && (strat == BTLessStrategyNumber || strat == BTLessEqualStrategyNumber)) @@ -536,7 +535,11 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) for (i = 0; i < keysCount; i++) { j = nKeyIs[i]; - /* _bt_orderkeys disallows it, but it's place to add some code later */ + + /* + * _bt_orderkeys disallows it, but it's place to add some code + * later + */ if (so->keyData[j].sk_flags & SK_ISNULL) { pfree(nKeyIs); @@ -562,7 +565,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) /* don't need to keep the stack around... */ _bt_freestack(stack); - if (! BufferIsValid(buf)) + if (!BufferIsValid(buf)) { /* Only get here if index is completely empty */ ItemPointerSetInvalid(current); @@ -601,6 +604,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) switch (strat_total) { case BTLessStrategyNumber: + /* * Back up one to arrive at last item < scankey */ @@ -612,6 +616,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) break; case BTLessEqualStrategyNumber: + /* * We need to find the last item <= scankey, so step forward * till we find one > scankey, then step back one. @@ -645,9 +650,10 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) break; case BTEqualStrategyNumber: + /* - * Make sure we are on the first equal item; might have to step - * forward if currently at end of page. + * Make sure we are on the first equal item; might have to + * step forward if currently at end of page. */ if (offnum > PageGetMaxOffsetNumber(page)) { @@ -661,7 +667,8 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) } result = _bt_compare(rel, keysCount, scankeys, page, offnum); if (result != 0) - goto nomatches; /* no equal items! */ + goto nomatches; /* no equal items! */ + /* * If a backward scan was specified, need to start with last * equal item not first one. @@ -685,6 +692,7 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) break; case BTGreaterEqualStrategyNumber: + /* * We want the first item >= scankey, which is where we are... * unless we're not anywhere at all... @@ -700,9 +708,10 @@ _bt_first(IndexScanDesc scan, ScanDirection dir) break; case BTGreaterStrategyNumber: + /* - * We want the first item > scankey, so make sure we are on - * an item and then step over any equal items. + * We want the first item > scankey, so make sure we are on an + * item and then step over any equal items. */ if (offnum > PageGetMaxOffsetNumber(page)) { @@ -850,11 +859,12 @@ _bt_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir) *bufP = _bt_getbuf(rel, blkno, BT_READ); page = BufferGetPage(*bufP); opaque = (BTPageOpaque) PageGetSpecialPointer(page); + /* * If the adjacent page just split, then we have to walk - * right to find the block that's now adjacent to where - * we were. Because pages only split right, we don't have - * to worry about this failing to terminate. + * right to find the block that's now adjacent to where we + * were. Because pages only split right, we don't have to + * worry about this failing to terminate. */ while (opaque->btpo_next != obknum) { @@ -912,12 +922,12 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir) /* * Scan down to the leftmost or rightmost leaf page. This is a - * simplified version of _bt_search(). We don't maintain a stack + * simplified version of _bt_search(). We don't maintain a stack * since we know we won't need it. */ buf = _bt_getroot(rel, BT_READ); - if (! BufferIsValid(buf)) + if (!BufferIsValid(buf)) { /* empty index... */ ItemPointerSetInvalid(current); @@ -981,7 +991,8 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir) Assert(P_RIGHTMOST(opaque)); start = PageGetMaxOffsetNumber(page); - if (start < P_FIRSTDATAKEY(opaque)) /* watch out for empty page */ + if (start < P_FIRSTDATAKEY(opaque)) /* watch out for empty + * page */ start = P_FIRSTDATAKEY(opaque); } else @@ -995,8 +1006,8 @@ _bt_endpoint(IndexScanDesc scan, ScanDirection dir) so->btso_curbuf = buf; /* - * Left/rightmost page could be empty due to deletions, - * if so step till we find a nonempty page. + * Left/rightmost page could be empty due to deletions, if so step + * till we find a nonempty page. */ if (start > maxoff) { diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c index e9224a485af..2aca6bf7cfc 100644 --- a/src/backend/access/nbtree/nbtsort.c +++ b/src/backend/access/nbtree/nbtsort.c @@ -6,7 +6,7 @@ * * We use tuplesort.c to sort the given index tuples into order. * Then we scan the index tuples in order and build the btree pages - * for each level. We load source tuples into leaf-level pages. + * for each level. We load source tuples into leaf-level pages. * Whenever we fill a page at one level, we add a link to it to its * parent level (starting a new parent level if necessary). When * done, we write out each final page on each level, adding it to @@ -35,7 +35,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.59 2001/01/24 19:42:49 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.60 2001/03/22 03:59:15 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -57,7 +57,7 @@ struct BTSpool }; /* - * Status record for a btree page being built. We have one of these + * Status record for a btree page being built. We have one of these * for each active tree level. * * The reason we need to store a copy of the minimum key is that we'll @@ -73,11 +73,13 @@ typedef struct BTPageState { Buffer btps_buf; /* current buffer & page */ Page btps_page; - BTItem btps_minkey; /* copy of minimum key (first item) on page */ + BTItem btps_minkey; /* copy of minimum key (first item) on + * page */ OffsetNumber btps_lastoff; /* last item offset loaded */ int btps_level; /* tree level (0 = leaf) */ - Size btps_full; /* "full" if less than this much free space */ - struct BTPageState *btps_next; /* link to parent level, if any */ + Size btps_full; /* "full" if less than this much free + * space */ + struct BTPageState *btps_next; /* link to parent level, if any */ } BTPageState; @@ -92,7 +94,7 @@ static void _bt_blnewpage(Relation index, Buffer *buf, Page *page, int flags); static BTPageState *_bt_pagestate(Relation index, int flags, int level); static void _bt_slideleft(Relation index, Buffer buf, Page page); static void _bt_sortaddtup(Page page, Size itemsize, - BTItem btitem, OffsetNumber itup_off); + BTItem btitem, OffsetNumber itup_off); static void _bt_buildadd(Relation index, BTPageState *state, BTItem bti); static void _bt_uppershutdown(Relation index, BTPageState *state); static void _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2); @@ -162,7 +164,7 @@ _bt_leafbuild(BTSpool *btspool, BTSpool *btspool2) ShowUsage(); ResetUsage(); } -#endif /* BTREE_BUILD_STATS */ +#endif /* BTREE_BUILD_STATS */ tuplesort_performsort(btspool->sortstate); if (btspool2) @@ -269,9 +271,9 @@ _bt_sortaddtup(Page page, OffsetNumber itup_off) { BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page); - BTItemData truncitem; + BTItemData truncitem; - if (! P_ISLEAF(opaque) && itup_off == P_FIRSTKEY) + if (!P_ISLEAF(opaque) && itup_off == P_FIRSTKEY) { memcpy(&truncitem, btitem, sizeof(BTItemData)); truncitem.bti_itup.t_info = sizeof(BTItemData); @@ -290,7 +292,7 @@ _bt_sortaddtup(Page page, * We must be careful to observe the page layout conventions of nbtsearch.c: * - rightmost pages start data items at P_HIKEY instead of at P_FIRSTKEY. * - on non-leaf pages, the key portion of the first item need not be - * stored, we should store only the link. + * stored, we should store only the link. * * A leaf page being built looks like: * @@ -347,11 +349,12 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti) */ if (btisz > (PageGetPageSize(npage) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) / 3 - sizeof(ItemIdData)) elog(ERROR, "btree: index item size %lu exceeds maximum %ld", - (unsigned long)btisz, - (PageGetPageSize(npage) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) /3 - sizeof(ItemIdData)); + (unsigned long) btisz, + (PageGetPageSize(npage) - sizeof(PageHeaderData) - MAXALIGN(sizeof(BTPageOpaqueData))) / 3 - sizeof(ItemIdData)); if (pgspc < btisz || pgspc < state->btps_full) { + /* * Item won't fit on this page, or we feel the page is full enough * already. Finish off the page and write it out. @@ -388,9 +391,9 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti) ((PageHeader) opage)->pd_lower -= sizeof(ItemIdData); /* - * Link the old buffer into its parent, using its minimum key. - * If we don't have a parent, we have to create one; - * this adds a new btree level. + * Link the old buffer into its parent, using its minimum key. If + * we don't have a parent, we have to create one; this adds a new + * btree level. */ if (state->btps_next == (BTPageState *) NULL) { @@ -405,8 +408,8 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti) /* * Save a copy of the minimum key for the new page. We have to - * copy it off the old page, not the new one, in case we are - * not at leaf level. + * copy it off the old page, not the new one, in case we are not + * at leaf level. */ state->btps_minkey = _bt_formitem(&(obti->bti_itup)); @@ -414,13 +417,13 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti) * Set the sibling links for both pages, and parent links too. * * It's not necessary to set the parent link at all, because it's - * only used for handling concurrent root splits, but we may as well - * do it as a debugging aid. Note we set new page's link as well - * as old's, because if the new page turns out to be the last of - * the level, _bt_uppershutdown won't change it. The links may be - * out of date by the time the build finishes, but that's OK; they - * need only point to a left-sibling of the true parent. See the - * README file for more info. + * only used for handling concurrent root splits, but we may as + * well do it as a debugging aid. Note we set new page's link as + * well as old's, because if the new page turns out to be the last + * of the level, _bt_uppershutdown won't change it. The links may + * be out of date by the time the build finishes, but that's OK; + * they need only point to a left-sibling of the true parent. See + * the README file for more info. */ { BTPageOpaque oopaque = (BTPageOpaque) PageGetSpecialPointer(opage); @@ -434,7 +437,7 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti) } /* - * Write out the old page. We never want to see it again, so we + * Write out the old page. We never want to see it again, so we * can give up our lock (if we had one; most likely BuildingBtree * is set, so we aren't locking). */ @@ -449,8 +452,8 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti) /* * If the new item is the first for its page, stash a copy for later. * Note this will only happen for the first item on a level; on later - * pages, the first item for a page is copied from the prior page - * in the code above. + * pages, the first item for a page is copied from the prior page in + * the code above. */ if (last_off == P_HIKEY) { @@ -493,8 +496,8 @@ _bt_uppershutdown(Relation index, BTPageState *state) * * If we're at the top, it's the root, so attach it to the metapage. * Otherwise, add an entry for it to its parent using its minimum - * key. This may cause the last page of the parent level to split, - * but that's not a problem -- we haven't gotten to it yet. + * key. This may cause the last page of the parent level to + * split, but that's not a problem -- we haven't gotten to it yet. */ if (s->btps_next == (BTPageState *) NULL) { @@ -513,7 +516,7 @@ _bt_uppershutdown(Relation index, BTPageState *state) /* * This is the rightmost page, so the ItemId array needs to be - * slid back one slot. Then we can dump out the page. + * slid back one slot. Then we can dump out the page. */ _bt_slideleft(index, s->btps_buf, s->btps_page); _bt_wrtbuf(index, s->btps_buf); @@ -529,22 +532,29 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2) { BTPageState *state = NULL; bool merge = (btspool2 != NULL); - BTItem bti, bti2 = NULL; - bool should_free, should_free2, load1; + BTItem bti, + bti2 = NULL; + bool should_free, + should_free2, + load1; TupleDesc tupdes = RelationGetDescr(index); - int i, keysz = RelationGetNumberOfAttributes(index); + int i, + keysz = RelationGetNumberOfAttributes(index); ScanKey indexScanKey = NULL; if (merge) { + /* - * Another BTSpool for dead tuples exists. - * Now we have to merge btspool and btspool2. - */ - ScanKey entry; - Datum attrDatum1, attrDatum2; - bool isFirstNull, isSecondNull; - int32 compare; + * Another BTSpool for dead tuples exists. Now we have to merge + * btspool and btspool2. + */ + ScanKey entry; + Datum attrDatum1, + attrDatum2; + bool isFirstNull, + isSecondNull; + int32 compare; /* the preparation of merge */ bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free); @@ -552,7 +562,7 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2) indexScanKey = _bt_mkscankey_nodata(index); for (;;) { - load1 = true; /* load BTSpool next ? */ + load1 = true; /* load BTSpool next ? */ if (NULL == bti2) { if (NULL == bti) @@ -564,8 +574,8 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2) for (i = 1; i <= keysz; i++) { entry = indexScanKey + i - 1; - attrDatum1 = index_getattr((IndexTuple)bti, i, tupdes, &isFirstNull); - attrDatum2 = index_getattr((IndexTuple)bti2, i, tupdes, &isSecondNull); + attrDatum1 = index_getattr((IndexTuple) bti, i, tupdes, &isFirstNull); + attrDatum2 = index_getattr((IndexTuple) bti2, i, tupdes, &isSecondNull); if (isFirstNull) { if (!isSecondNull) @@ -586,7 +596,7 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2) } else if (compare < 0) break; - } + } } } else @@ -613,7 +623,8 @@ _bt_load(Relation index, BTSpool *btspool, BTSpool *btspool2) } _bt_freeskey(indexScanKey); } - else /* merge is unnecessary */ + else +/* merge is unnecessary */ { while (bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true, &should_free), bti != (BTItem) NULL) { diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c index 507205f2be7..2a37147d68e 100644 --- a/src/backend/access/nbtree/nbtutils.c +++ b/src/backend/access/nbtree/nbtutils.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.42 2001/01/24 19:42:49 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.43 2001/03/22 03:59:15 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -124,7 +124,7 @@ _bt_freestack(BTStack stack) * Construct a BTItem from a plain IndexTuple. * * This is now useless code, since a BTItem *is* an index tuple with - * no extra stuff. We hang onto it for the moment to preserve the + * no extra stuff. We hang onto it for the moment to preserve the * notational distinction, in case we want to add some extra stuff * again someday. */ @@ -165,7 +165,7 @@ _bt_formitem(IndexTuple itup) * are "x = 1 AND y < 4 AND z < 5", then _bt_checkkeys will reject a tuple * (1,2,7), but we must continue the scan in case there are tuples (1,3,z). * But once we reach tuples like (1,4,z) we can stop scanning because no - * later tuples could match. This is reflected by setting + * later tuples could match. This is reflected by setting * so->numberOfRequiredKeys to the number of leading keys that must be * matched to continue the scan. numberOfRequiredKeys is equal to the * number of leading "=" keys plus the key(s) for the first non "=" @@ -178,7 +178,7 @@ _bt_formitem(IndexTuple itup) * * XXX this routine is one of many places that fail to handle SK_COMMUTE * scankeys properly. Currently, the planner is careful never to generate - * any indexquals that would require SK_COMMUTE to be set. Someday we ought + * any indexquals that would require SK_COMMUTE to be set. Someday we ought * to try to fix this, though it's not real critical as long as indexable * operators all have commutators... * @@ -191,7 +191,7 @@ _bt_formitem(IndexTuple itup) void _bt_orderkeys(Relation relation, BTScanOpaque so) { - ScanKeyData xform[BTMaxStrategyNumber]; + ScanKeyData xform[BTMaxStrategyNumber]; bool init[BTMaxStrategyNumber]; uint16 numberOfKeys = so->numberOfKeys; ScanKey key; @@ -240,14 +240,14 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) /* * Initialize for processing of keys for attr 1. * - * xform[i] holds a copy of the current scan key of strategy type i+1, - * if any; init[i] is TRUE if we have found such a key for this attr. + * xform[i] holds a copy of the current scan key of strategy type i+1, if + * any; init[i] is TRUE if we have found such a key for this attr. */ attno = 1; map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation), BTMaxStrategyNumber, attno); - MemSet(xform, 0, sizeof(xform)); /* not really necessary */ + MemSet(xform, 0, sizeof(xform)); /* not really necessary */ MemSet(init, 0, sizeof(init)); /* @@ -255,7 +255,7 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) * pass to handle after-last-key processing. Actual exit from the * loop is at the "break" statement below. */ - for (i = 0; ; cur++, i++) + for (i = 0;; cur++, i++) { if (i < numberOfKeys) { @@ -263,7 +263,9 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) if (cur->sk_flags & SK_ISNULL) { so->qual_ok = false; - /* Quit processing so we don't try to invoke comparison + + /* + * Quit processing so we don't try to invoke comparison * routines on NULLs. */ return; @@ -271,8 +273,8 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) } /* - * If we are at the end of the keys for a particular attr, - * finish up processing and emit the cleaned-up keys. + * If we are at the end of the keys for a particular attr, finish + * up processing and emit the cleaned-up keys. */ if (i == numberOfKeys || cur->sk_attno != attno) { @@ -296,7 +298,7 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) eq = &xform[BTEqualStrategyNumber - 1]; for (j = BTMaxStrategyNumber; --j >= 0;) { - if (! init[j] || + if (!init[j] || j == (BTEqualStrategyNumber - 1)) continue; chk = &xform[j]; @@ -313,6 +315,7 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) } else { + /* * No "=" for this key, so we're done with required keys */ @@ -355,8 +358,8 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) * Emit the cleaned-up keys back into the key[] array in the * correct order. Note we are overwriting our input here! * It's OK because (a) xform[] is a physical copy of the keys - * we want, (b) we cannot emit more keys than we input, so - * we won't overwrite as-yet-unprocessed keys. + * we want, (b) we cannot emit more keys than we input, so we + * won't overwrite as-yet-unprocessed keys. */ for (j = BTMaxStrategyNumber; --j >= 0;) { @@ -383,7 +386,7 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) map = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(relation), BTMaxStrategyNumber, attno); - MemSet(xform, 0, sizeof(xform)); /* not really necessary */ + MemSet(xform, 0, sizeof(xform)); /* not really necessary */ MemSet(init, 0, sizeof(init)); } @@ -409,7 +412,8 @@ _bt_orderkeys(Relation relation, BTScanOpaque so) if (DatumGetBool(test)) xform[j].sk_argument = cur->sk_argument; else if (j == (BTEqualStrategyNumber - 1)) - so->qual_ok = false; /* key == a && key == b, but a != b */ + so->qual_ok = false; /* key == a && key == b, but a != + * b */ } else { @@ -473,16 +477,18 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, if (isNull) { + /* * Since NULLs are sorted after non-NULLs, we know we have * reached the upper limit of the range of values for this - * index attr. On a forward scan, we can stop if this qual - * is one of the "must match" subset. On a backward scan, + * index attr. On a forward scan, we can stop if this qual is + * one of the "must match" subset. On a backward scan, * however, we should keep going. */ if (keysok < so->numberOfRequiredKeys && ScanDirectionIsForward(dir)) *continuescan = false; + /* * In any case, this indextuple doesn't match the qual. */ @@ -498,9 +504,10 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, if (DatumGetBool(test) == !!(key->sk_flags & SK_NEGATE)) { + /* - * Tuple fails this qual. If it's a required qual, then - * we can conclude no further tuples will pass, either. + * Tuple fails this qual. If it's a required qual, then we + * can conclude no further tuples will pass, either. */ if (keysok < so->numberOfRequiredKeys) *continuescan = false; |