bt_delete.c revision 14272
11573Srgrimes/*- 214272Spst * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Mike Olson. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 3. All advertising materials mentioning features or use of this software 171573Srgrimes * must display the following acknowledgement: 181573Srgrimes * This product includes software developed by the University of 191573Srgrimes * California, Berkeley and its contributors. 201573Srgrimes * 4. Neither the name of the University nor the names of its contributors 211573Srgrimes * may be used to endorse or promote products derived from this software 221573Srgrimes * without specific prior written permission. 231573Srgrimes * 241573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341573Srgrimes * SUCH DAMAGE. 351573Srgrimes */ 361573Srgrimes 371573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3814272Spststatic char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94"; 391573Srgrimes#endif /* LIBC_SCCS and not lint */ 401573Srgrimes 411573Srgrimes#include <sys/types.h> 421573Srgrimes 431573Srgrimes#include <errno.h> 441573Srgrimes#include <stdio.h> 451573Srgrimes#include <string.h> 461573Srgrimes 471573Srgrimes#include <db.h> 481573Srgrimes#include "btree.h" 491573Srgrimes 5014272Spststatic int __bt_bdelete __P((BTREE *, const DBT *)); 5114272Spststatic int __bt_curdel __P((BTREE *, const DBT *, PAGE *, u_int)); 5214272Spststatic int __bt_pdelete __P((BTREE *, PAGE *)); 5314272Spststatic int __bt_relink __P((BTREE *, PAGE *)); 5414272Spststatic int __bt_stkacq __P((BTREE *, PAGE **, CURSOR *)); 551573Srgrimes 561573Srgrimes/* 5714272Spst * __bt_delete 5814272Spst * Delete the item(s) referenced by a key. 591573Srgrimes * 6014272Spst * Return RET_SPECIAL if the key is not found. 611573Srgrimes */ 621573Srgrimesint 631573Srgrimes__bt_delete(dbp, key, flags) 641573Srgrimes const DB *dbp; 651573Srgrimes const DBT *key; 661573Srgrimes u_int flags; 671573Srgrimes{ 681573Srgrimes BTREE *t; 6914272Spst CURSOR *c; 7014272Spst PAGE *h; 711573Srgrimes int status; 721573Srgrimes 731573Srgrimes t = dbp->internal; 741573Srgrimes 751573Srgrimes /* Toss any page pinned across calls. */ 761573Srgrimes if (t->bt_pinned != NULL) { 771573Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 781573Srgrimes t->bt_pinned = NULL; 791573Srgrimes } 801573Srgrimes 8114272Spst /* Check for change to a read-only tree. */ 8214272Spst if (F_ISSET(t, B_RDONLY)) { 831573Srgrimes errno = EPERM; 841573Srgrimes return (RET_ERROR); 851573Srgrimes } 861573Srgrimes 8714272Spst switch (flags) { 881573Srgrimes case 0: 8914272Spst status = __bt_bdelete(t, key); 901573Srgrimes break; 911573Srgrimes case R_CURSOR: 921573Srgrimes /* 9314272Spst * If flags is R_CURSOR, delete the cursor. Must already 9414272Spst * have started a scan and not have already deleted it. 951573Srgrimes */ 9614272Spst c = &t->bt_cursor; 9714272Spst if (F_ISSET(c, CURS_INIT)) { 9814272Spst if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) 9914272Spst return (RET_SPECIAL); 10014272Spst if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) 10114272Spst return (RET_ERROR); 10214272Spst 10314272Spst /* 10414272Spst * If the page is about to be emptied, we'll need to 10514272Spst * delete it, which means we have to acquire a stack. 10614272Spst */ 10714272Spst if (NEXTINDEX(h) == 1) 10814272Spst if (__bt_stkacq(t, &h, &t->bt_cursor)) 10914272Spst return (RET_ERROR); 11014272Spst 11114272Spst status = __bt_dleaf(t, NULL, h, c->pg.index); 11214272Spst 11314272Spst if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) { 11414272Spst if (__bt_pdelete(t, h)) 11514272Spst return (RET_ERROR); 11614272Spst } else 11714272Spst mpool_put(t->bt_mp, 11814272Spst h, status == RET_SUCCESS ? MPOOL_DIRTY : 0); 11914272Spst break; 12014272Spst } 12114272Spst /* FALLTHROUGH */ 1221573Srgrimes default: 12314272Spst errno = EINVAL; 1241573Srgrimes return (RET_ERROR); 1251573Srgrimes } 1261573Srgrimes if (status == RET_SUCCESS) 12714272Spst F_SET(t, B_MODIFIED); 1281573Srgrimes return (status); 1291573Srgrimes} 1301573Srgrimes 1311573Srgrimes/* 13214272Spst * __bt_stkacq -- 13314272Spst * Acquire a stack so we can delete a cursor entry. 1341573Srgrimes * 1351573Srgrimes * Parameters: 13614272Spst * t: tree 13714272Spst * hp: pointer to current, pinned PAGE pointer 13814272Spst * c: pointer to the cursor 13914272Spst * 14014272Spst * Returns: 14114272Spst * 0 on success, 1 on failure 14214272Spst */ 14314272Spststatic int 14414272Spst__bt_stkacq(t, hp, c) 14514272Spst BTREE *t; 14614272Spst PAGE **hp; 14714272Spst CURSOR *c; 14814272Spst{ 14914272Spst BINTERNAL *bi; 15014272Spst EPG *e; 15114272Spst EPGNO *parent; 15214272Spst PAGE *h; 15314272Spst indx_t index; 15414272Spst pgno_t pgno; 15514272Spst recno_t nextpg, prevpg; 15614272Spst int exact, level; 15714272Spst 15814272Spst /* 15914272Spst * Find the first occurrence of the key in the tree. Toss the 16014272Spst * currently locked page so we don't hit an already-locked page. 16114272Spst */ 16214272Spst h = *hp; 16314272Spst mpool_put(t->bt_mp, h, 0); 16414272Spst if ((e = __bt_search(t, &c->key, &exact)) == NULL) 16514272Spst return (1); 16614272Spst h = e->page; 16714272Spst 16814272Spst /* See if we got it in one shot. */ 16914272Spst if (h->pgno == c->pg.pgno) 17014272Spst goto ret; 17114272Spst 17214272Spst /* 17314272Spst * Move right, looking for the page. At each move we have to move 17414272Spst * up the stack until we don't have to move to the next page. If 17514272Spst * we have to change pages at an internal level, we have to fix the 17614272Spst * stack back up. 17714272Spst */ 17814272Spst while (h->pgno != c->pg.pgno) { 17914272Spst if ((nextpg = h->nextpg) == P_INVALID) 18014272Spst break; 18114272Spst mpool_put(t->bt_mp, h, 0); 18214272Spst 18314272Spst /* Move up the stack. */ 18414272Spst for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 18514272Spst /* Get the parent page. */ 18614272Spst if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 18714272Spst return (1); 18814272Spst 18914272Spst /* Move to the next index. */ 19014272Spst if (parent->index != NEXTINDEX(h) - 1) { 19114272Spst index = parent->index + 1; 19214272Spst BT_PUSH(t, h->pgno, index); 19314272Spst break; 19414272Spst } 19514272Spst mpool_put(t->bt_mp, h, 0); 19614272Spst } 19714272Spst 19814272Spst /* Restore the stack. */ 19914272Spst while (level--) { 20014272Spst /* Push the next level down onto the stack. */ 20114272Spst bi = GETBINTERNAL(h, index); 20214272Spst pgno = bi->pgno; 20314272Spst BT_PUSH(t, pgno, 0); 20414272Spst 20514272Spst /* Lose the currently pinned page. */ 20614272Spst mpool_put(t->bt_mp, h, 0); 20714272Spst 20814272Spst /* Get the next level down. */ 20914272Spst if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 21014272Spst return (1); 21114272Spst index = 0; 21214272Spst } 21314272Spst mpool_put(t->bt_mp, h, 0); 21414272Spst if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL) 21514272Spst return (1); 21614272Spst } 21714272Spst 21814272Spst if (h->pgno == c->pg.pgno) 21914272Spst goto ret; 22014272Spst 22114272Spst /* Reacquire the original stack. */ 22214272Spst mpool_put(t->bt_mp, h, 0); 22314272Spst if ((e = __bt_search(t, &c->key, &exact)) == NULL) 22414272Spst return (1); 22514272Spst h = e->page; 22614272Spst 22714272Spst /* 22814272Spst * Move left, looking for the page. At each move we have to move 22914272Spst * up the stack until we don't have to change pages to move to the 23014272Spst * next page. If we have to change pages at an internal level, we 23114272Spst * have to fix the stack back up. 23214272Spst */ 23314272Spst while (h->pgno != c->pg.pgno) { 23414272Spst if ((prevpg = h->prevpg) == P_INVALID) 23514272Spst break; 23614272Spst mpool_put(t->bt_mp, h, 0); 23714272Spst 23814272Spst /* Move up the stack. */ 23914272Spst for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 24014272Spst /* Get the parent page. */ 24114272Spst if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 24214272Spst return (1); 24314272Spst 24414272Spst /* Move to the next index. */ 24514272Spst if (parent->index != 0) { 24614272Spst index = parent->index - 1; 24714272Spst BT_PUSH(t, h->pgno, index); 24814272Spst break; 24914272Spst } 25014272Spst mpool_put(t->bt_mp, h, 0); 25114272Spst } 25214272Spst 25314272Spst /* Restore the stack. */ 25414272Spst while (level--) { 25514272Spst /* Push the next level down onto the stack. */ 25614272Spst bi = GETBINTERNAL(h, index); 25714272Spst pgno = bi->pgno; 25814272Spst 25914272Spst /* Lose the currently pinned page. */ 26014272Spst mpool_put(t->bt_mp, h, 0); 26114272Spst 26214272Spst /* Get the next level down. */ 26314272Spst if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 26414272Spst return (1); 26514272Spst 26614272Spst index = NEXTINDEX(h) - 1; 26714272Spst BT_PUSH(t, pgno, index); 26814272Spst } 26914272Spst mpool_put(t->bt_mp, h, 0); 27014272Spst if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL) 27114272Spst return (1); 27214272Spst } 27314272Spst 27414272Spst 27514272Spstret: mpool_put(t->bt_mp, h, 0); 27614272Spst return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL); 27714272Spst} 27814272Spst 27914272Spst/* 28014272Spst * __bt_bdelete -- 28114272Spst * Delete all key/data pairs matching the specified key. 28214272Spst * 28314272Spst * Parameters: 28414272Spst * t: tree 2851573Srgrimes * key: key to delete 2861573Srgrimes * 2871573Srgrimes * Returns: 2881573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 2891573Srgrimes */ 2901573Srgrimesstatic int 29114272Spst__bt_bdelete(t, key) 2921573Srgrimes BTREE *t; 2931573Srgrimes const DBT *key; 2941573Srgrimes{ 29514272Spst EPG *e; 2961573Srgrimes PAGE *h; 29714272Spst int deleted, exact, redo; 2981573Srgrimes 29914272Spst deleted = 0; 30014272Spst 3011573Srgrimes /* Find any matching record; __bt_search pins the page. */ 30214272Spstloop: if ((e = __bt_search(t, key, &exact)) == NULL) 30314272Spst return (deleted ? RET_SUCCESS : RET_ERROR); 3041573Srgrimes if (!exact) { 3051573Srgrimes mpool_put(t->bt_mp, e->page, 0); 30614272Spst return (deleted ? RET_SUCCESS : RET_SPECIAL); 3071573Srgrimes } 3081573Srgrimes 3091573Srgrimes /* 31014272Spst * Delete forward, then delete backward, from the found key. If 31114272Spst * there are duplicates and we reach either side of the page, do 31214272Spst * the key search again, so that we get them all. 3131573Srgrimes */ 31414272Spst redo = 0; 31514272Spst h = e->page; 31614272Spst do { 31714272Spst if (__bt_dleaf(t, key, h, e->index)) { 31814272Spst mpool_put(t->bt_mp, h, 0); 31914272Spst return (RET_ERROR); 32014272Spst } 32114272Spst if (F_ISSET(t, B_NODUPS)) { 32214272Spst if (NEXTINDEX(h) == 0) { 32314272Spst if (__bt_pdelete(t, h)) 3241573Srgrimes return (RET_ERROR); 32514272Spst } else 32614272Spst mpool_put(t->bt_mp, h, MPOOL_DIRTY); 32714272Spst return (RET_SUCCESS); 3281573Srgrimes } 32914272Spst deleted = 1; 33014272Spst } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); 3311573Srgrimes 33214272Spst /* Check for right-hand edge of the page. */ 33314272Spst if (e->index == NEXTINDEX(h)) 33414272Spst redo = 1; 33514272Spst 33614272Spst /* Delete from the key to the beginning of the page. */ 33714272Spst while (e->index-- > 0) { 3381573Srgrimes if (__bt_cmp(t, key, e) != 0) 3391573Srgrimes break; 34014272Spst if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) { 34114272Spst mpool_put(t->bt_mp, h, 0); 34214272Spst return (RET_ERROR); 34314272Spst } 34414272Spst if (e->index == 0) 34514272Spst redo = 1; 3461573Srgrimes } 3471573Srgrimes 34814272Spst /* Check for an empty page. */ 34914272Spst if (NEXTINDEX(h) == 0) { 35014272Spst if (__bt_pdelete(t, h)) 35114272Spst return (RET_ERROR); 35214272Spst goto loop; 35314272Spst } 35414272Spst 35514272Spst /* Put the page. */ 35614272Spst mpool_put(t->bt_mp, h, MPOOL_DIRTY); 35714272Spst 35814272Spst if (redo) 35914272Spst goto loop; 36014272Spst return (RET_SUCCESS); 36114272Spst} 36214272Spst 36314272Spst/* 36414272Spst * __bt_pdelete -- 36514272Spst * Delete a single page from the tree. 36614272Spst * 36714272Spst * Parameters: 36814272Spst * t: tree 36914272Spst * h: leaf page 37014272Spst * 37114272Spst * Returns: 37214272Spst * RET_SUCCESS, RET_ERROR. 37314272Spst * 37414272Spst * Side-effects: 37514272Spst * mpool_put's the page 37614272Spst */ 37714272Spststatic int 37814272Spst__bt_pdelete(t, h) 37914272Spst BTREE *t; 38014272Spst PAGE *h; 38114272Spst{ 38214272Spst BINTERNAL *bi; 38314272Spst PAGE *pg; 38414272Spst EPGNO *parent; 38514272Spst indx_t cnt, index, *ip, offset; 38614272Spst u_int32_t nksize; 38714272Spst char *from; 38814272Spst 3891573Srgrimes /* 39014272Spst * Walk the parent page stack -- a LIFO stack of the pages that were 39114272Spst * traversed when we searched for the page where the delete occurred. 39214272Spst * Each stack entry is a page number and a page index offset. The 39314272Spst * offset is for the page traversed on the search. We've just deleted 39414272Spst * a page, so we have to delete the key from the parent page. 39514272Spst * 39614272Spst * If the delete from the parent page makes it empty, this process may 39714272Spst * continue all the way up the tree. We stop if we reach the root page 39814272Spst * (which is never deleted, it's just not worth the effort) or if the 39914272Spst * delete does not empty the page. 4001573Srgrimes */ 40114272Spst while ((parent = BT_POP(t)) != NULL) { 40214272Spst /* Get the parent page. */ 40314272Spst if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 40414272Spst return (RET_ERROR); 40514272Spst 40614272Spst index = parent->index; 40714272Spst bi = GETBINTERNAL(pg, index); 4081573Srgrimes 40914272Spst /* Free any overflow pages. */ 41014272Spst if (bi->flags & P_BIGKEY && 41114272Spst __ovfl_delete(t, bi->bytes) == RET_ERROR) { 41214272Spst mpool_put(t->bt_mp, pg, 0); 41314272Spst return (RET_ERROR); 41414272Spst } 41514272Spst 41614272Spst /* 41714272Spst * Free the parent if it has only the one key and it's not the 41814272Spst * root page. If it's the rootpage, turn it back into an empty 41914272Spst * leaf page. 42014272Spst */ 42114272Spst if (NEXTINDEX(pg) == 1) 42214272Spst if (pg->pgno == P_ROOT) { 42314272Spst pg->lower = BTDATAOFF; 42414272Spst pg->upper = t->bt_psize; 42514272Spst pg->flags = P_BLEAF; 4261573Srgrimes } else { 42714272Spst if (__bt_relink(t, pg) || __bt_free(t, pg)) 4281573Srgrimes return (RET_ERROR); 42914272Spst continue; 4301573Srgrimes } 43114272Spst else { 43214272Spst /* Pack remaining key items at the end of the page. */ 43314272Spst nksize = NBINTERNAL(bi->ksize); 43414272Spst from = (char *)pg + pg->upper; 43514272Spst memmove(from + nksize, from, (char *)bi - from); 43614272Spst pg->upper += nksize; 43714272Spst 43814272Spst /* Adjust indices' offsets, shift the indices down. */ 43914272Spst offset = pg->linp[index]; 44014272Spst for (cnt = index, ip = &pg->linp[0]; cnt--; ++ip) 44114272Spst if (ip[0] < offset) 44214272Spst ip[0] += nksize; 44314272Spst for (cnt = NEXTINDEX(pg) - index; --cnt; ++ip) 44414272Spst ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1]; 44514272Spst pg->lower -= sizeof(indx_t); 4461573Srgrimes } 4471573Srgrimes 44814272Spst mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 44914272Spst break; 4501573Srgrimes } 4511573Srgrimes 45214272Spst /* Free the leaf page, as long as it wasn't the root. */ 45314272Spst if (h->pgno == P_ROOT) { 45414272Spst mpool_put(t->bt_mp, h, MPOOL_DIRTY); 45514272Spst return (RET_SUCCESS); 45614272Spst } 45714272Spst return (__bt_relink(t, h) || __bt_free(t, h)); 4581573Srgrimes} 4591573Srgrimes 4601573Srgrimes/* 46114272Spst * __bt_dleaf -- 46214272Spst * Delete a single record from a leaf page. 4631573Srgrimes * 4641573Srgrimes * Parameters: 4651573Srgrimes * t: tree 46614272Spst * key: referenced key 46714272Spst * h: page 46814272Spst * index: index on page to delete 4691573Srgrimes * 4701573Srgrimes * Returns: 4711573Srgrimes * RET_SUCCESS, RET_ERROR. 4721573Srgrimes */ 4731573Srgrimesint 47414272Spst__bt_dleaf(t, key, h, index) 4751573Srgrimes BTREE *t; 47614272Spst const DBT *key; 4771573Srgrimes PAGE *h; 47814272Spst u_int index; 4791573Srgrimes{ 48014272Spst BLEAF *bl; 48114272Spst indx_t cnt, *ip, offset; 48214272Spst u_int32_t nbytes; 48314272Spst void *to; 4841573Srgrimes char *from; 4851573Srgrimes 48614272Spst /* If this record is referenced by the cursor, delete the cursor. */ 48714272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 48814272Spst !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 48914272Spst t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == index && 49014272Spst __bt_curdel(t, key, h, index)) 49114272Spst return (RET_ERROR); 49214272Spst 49314272Spst /* If the entry uses overflow pages, make them available for reuse. */ 4941573Srgrimes to = bl = GETBLEAF(h, index); 4951573Srgrimes if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) 4961573Srgrimes return (RET_ERROR); 4971573Srgrimes if (bl->flags & P_BIGDATA && 4981573Srgrimes __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) 4991573Srgrimes return (RET_ERROR); 50014272Spst 50114272Spst /* Pack the remaining key/data items at the end of the page. */ 5021573Srgrimes nbytes = NBLEAF(bl); 5031573Srgrimes from = (char *)h + h->upper; 5041573Srgrimes memmove(from + nbytes, from, (char *)to - from); 5051573Srgrimes h->upper += nbytes; 5061573Srgrimes 50714272Spst /* Adjust the indices' offsets, shift the indices down. */ 5081573Srgrimes offset = h->linp[index]; 5091573Srgrimes for (cnt = index, ip = &h->linp[0]; cnt--; ++ip) 5101573Srgrimes if (ip[0] < offset) 5111573Srgrimes ip[0] += nbytes; 5121573Srgrimes for (cnt = NEXTINDEX(h) - index; --cnt; ++ip) 5131573Srgrimes ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 5141573Srgrimes h->lower -= sizeof(indx_t); 51514272Spst 51614272Spst /* If the cursor is on this page, adjust it as necessary. */ 51714272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 51814272Spst !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 51914272Spst t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > index) 52014272Spst --t->bt_cursor.pg.index; 52114272Spst 5221573Srgrimes return (RET_SUCCESS); 5231573Srgrimes} 52414272Spst 52514272Spst/* 52614272Spst * __bt_curdel -- 52714272Spst * Delete the cursor. 52814272Spst * 52914272Spst * Parameters: 53014272Spst * t: tree 53114272Spst * key: referenced key (or NULL) 53214272Spst * h: page 53314272Spst * index: index on page to delete 53414272Spst * 53514272Spst * Returns: 53614272Spst * RET_SUCCESS, RET_ERROR. 53714272Spst */ 53814272Spststatic int 53914272Spst__bt_curdel(t, key, h, index) 54014272Spst BTREE *t; 54114272Spst const DBT *key; 54214272Spst PAGE *h; 54314272Spst u_int index; 54414272Spst{ 54514272Spst CURSOR *c; 54614272Spst EPG e; 54714272Spst PAGE *pg; 54814272Spst int curcopy, status; 54914272Spst 55014272Spst /* 55114272Spst * If there are duplicates, move forward or backward to one. 55214272Spst * Otherwise, copy the key into the cursor area. 55314272Spst */ 55414272Spst c = &t->bt_cursor; 55514272Spst F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE); 55614272Spst 55714272Spst curcopy = 0; 55814272Spst if (!F_ISSET(t, B_NODUPS)) { 55914272Spst /* 56014272Spst * We're going to have to do comparisons. If we weren't 56114272Spst * provided a copy of the key, i.e. the user is deleting 56214272Spst * the current cursor position, get one. 56314272Spst */ 56414272Spst if (key == NULL) { 56514272Spst e.page = h; 56614272Spst e.index = index; 56714272Spst if ((status = __bt_ret(t, &e, 56814272Spst &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS) 56914272Spst return (status); 57014272Spst curcopy = 1; 57114272Spst key = &c->key; 57214272Spst } 57314272Spst /* Check previous key, if not at the beginning of the page. */ 57414272Spst if (index > 0) { 57514272Spst e.page = h; 57614272Spst e.index = index - 1; 57714272Spst if (__bt_cmp(t, key, &e) == 0) { 57814272Spst F_SET(c, CURS_BEFORE); 57914272Spst goto dup2; 58014272Spst } 58114272Spst } 58214272Spst /* Check next key, if not at the end of the page. */ 58314272Spst if (index < NEXTINDEX(h) - 1) { 58414272Spst e.page = h; 58514272Spst e.index = index + 1; 58614272Spst if (__bt_cmp(t, key, &e) == 0) { 58714272Spst F_SET(c, CURS_AFTER); 58814272Spst goto dup2; 58914272Spst } 59014272Spst } 59114272Spst /* Check previous key if at the beginning of the page. */ 59214272Spst if (index == 0 && h->prevpg != P_INVALID) { 59314272Spst if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) 59414272Spst return (RET_ERROR); 59514272Spst e.page = pg; 59614272Spst e.index = NEXTINDEX(pg) - 1; 59714272Spst if (__bt_cmp(t, key, &e) == 0) { 59814272Spst F_SET(c, CURS_BEFORE); 59914272Spst goto dup1; 60014272Spst } 60114272Spst mpool_put(t->bt_mp, pg, 0); 60214272Spst } 60314272Spst /* Check next key if at the end of the page. */ 60414272Spst if (index == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) { 60514272Spst if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) 60614272Spst return (RET_ERROR); 60714272Spst e.page = pg; 60814272Spst e.index = 0; 60914272Spst if (__bt_cmp(t, key, &e) == 0) { 61014272Spst F_SET(c, CURS_AFTER); 61114272Spstdup1: mpool_put(t->bt_mp, pg, 0); 61214272Spstdup2: c->pg.pgno = e.page->pgno; 61314272Spst c->pg.index = e.index; 61414272Spst return (RET_SUCCESS); 61514272Spst } 61614272Spst mpool_put(t->bt_mp, pg, 0); 61714272Spst } 61814272Spst } 61914272Spst e.page = h; 62014272Spst e.index = index; 62114272Spst if (curcopy || (status = 62214272Spst __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) { 62314272Spst F_SET(c, CURS_ACQUIRE); 62414272Spst return (RET_SUCCESS); 62514272Spst } 62614272Spst return (status); 62714272Spst} 62814272Spst 62914272Spst/* 63014272Spst * __bt_relink -- 63114272Spst * Link around a deleted page. 63214272Spst * 63314272Spst * Parameters: 63414272Spst * t: tree 63514272Spst * h: page to be deleted 63614272Spst */ 63714272Spststatic int 63814272Spst__bt_relink(t, h) 63914272Spst BTREE *t; 64014272Spst PAGE *h; 64114272Spst{ 64214272Spst PAGE *pg; 64314272Spst 64414272Spst if (h->nextpg != P_INVALID) { 64514272Spst if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) 64614272Spst return (RET_ERROR); 64714272Spst pg->prevpg = h->prevpg; 64814272Spst mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 64914272Spst } 65014272Spst if (h->prevpg != P_INVALID) { 65114272Spst if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) 65214272Spst return (RET_ERROR); 65314272Spst pg->nextpg = h->nextpg; 65414272Spst mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 65514272Spst } 65614272Spst return (0); 65714272Spst} 658