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 * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3414272Spststatic char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692905Sobrien#include <sys/cdefs.h> 3792905Sobrien__FBSDID("$FreeBSD: releng/11.0/lib/libc/db/btree/bt_delete.c 189327 2009-03-04 00:58:04Z delphij $"); 381573Srgrimes 391573Srgrimes#include <sys/types.h> 401573Srgrimes 411573Srgrimes#include <errno.h> 421573Srgrimes#include <stdio.h> 431573Srgrimes#include <string.h> 441573Srgrimes 451573Srgrimes#include <db.h> 461573Srgrimes#include "btree.h" 471573Srgrimes 4892905Sobrienstatic int __bt_bdelete(BTREE *, const DBT *); 4992905Sobrienstatic int __bt_curdel(BTREE *, const DBT *, PAGE *, u_int); 5092905Sobrienstatic int __bt_pdelete(BTREE *, PAGE *); 5192905Sobrienstatic int __bt_relink(BTREE *, PAGE *); 5292905Sobrienstatic int __bt_stkacq(BTREE *, PAGE **, CURSOR *); 531573Srgrimes 541573Srgrimes/* 5514272Spst * __bt_delete 5614272Spst * Delete the item(s) referenced by a key. 571573Srgrimes * 5814272Spst * Return RET_SPECIAL if the key is not found. 591573Srgrimes */ 601573Srgrimesint 61189291Sdelphij__bt_delete(const DB *dbp, const DBT *key, u_int flags) 621573Srgrimes{ 631573Srgrimes BTREE *t; 6414272Spst CURSOR *c; 6514272Spst PAGE *h; 661573Srgrimes int status; 671573Srgrimes 681573Srgrimes t = dbp->internal; 691573Srgrimes 701573Srgrimes /* Toss any page pinned across calls. */ 711573Srgrimes if (t->bt_pinned != NULL) { 721573Srgrimes mpool_put(t->bt_mp, t->bt_pinned, 0); 731573Srgrimes t->bt_pinned = NULL; 741573Srgrimes } 751573Srgrimes 7614272Spst /* Check for change to a read-only tree. */ 7714272Spst if (F_ISSET(t, B_RDONLY)) { 781573Srgrimes errno = EPERM; 791573Srgrimes return (RET_ERROR); 801573Srgrimes } 811573Srgrimes 8214272Spst switch (flags) { 831573Srgrimes case 0: 8414272Spst status = __bt_bdelete(t, key); 851573Srgrimes break; 861573Srgrimes case R_CURSOR: 871573Srgrimes /* 8814272Spst * If flags is R_CURSOR, delete the cursor. Must already 8914272Spst * have started a scan and not have already deleted it. 901573Srgrimes */ 9114272Spst c = &t->bt_cursor; 9214272Spst if (F_ISSET(c, CURS_INIT)) { 9314272Spst if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) 9414272Spst return (RET_SPECIAL); 9514272Spst if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) 9614272Spst return (RET_ERROR); 9714272Spst 9814272Spst /* 9914272Spst * If the page is about to be emptied, we'll need to 10014272Spst * delete it, which means we have to acquire a stack. 10114272Spst */ 10214272Spst if (NEXTINDEX(h) == 1) 10314272Spst if (__bt_stkacq(t, &h, &t->bt_cursor)) 10414272Spst return (RET_ERROR); 10514272Spst 10614272Spst status = __bt_dleaf(t, NULL, h, c->pg.index); 10714272Spst 10814272Spst if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) { 10914272Spst if (__bt_pdelete(t, h)) 11014272Spst return (RET_ERROR); 11114272Spst } else 11214272Spst mpool_put(t->bt_mp, 11314272Spst h, status == RET_SUCCESS ? MPOOL_DIRTY : 0); 11414272Spst break; 11514272Spst } 11614272Spst /* FALLTHROUGH */ 1171573Srgrimes default: 11814272Spst errno = EINVAL; 1191573Srgrimes return (RET_ERROR); 1201573Srgrimes } 1211573Srgrimes if (status == RET_SUCCESS) 12214272Spst F_SET(t, B_MODIFIED); 1231573Srgrimes return (status); 1241573Srgrimes} 1251573Srgrimes 1261573Srgrimes/* 12714272Spst * __bt_stkacq -- 12814272Spst * Acquire a stack so we can delete a cursor entry. 1291573Srgrimes * 1301573Srgrimes * Parameters: 13114272Spst * t: tree 13214272Spst * hp: pointer to current, pinned PAGE pointer 13314272Spst * c: pointer to the cursor 13414272Spst * 13514272Spst * Returns: 13614272Spst * 0 on success, 1 on failure 13714272Spst */ 13814272Spststatic int 139189291Sdelphij__bt_stkacq(BTREE *t, PAGE **hp, CURSOR *c) 14014272Spst{ 14114272Spst BINTERNAL *bi; 14214272Spst EPG *e; 14314272Spst EPGNO *parent; 14414272Spst PAGE *h; 145189292Sdelphij indx_t idx; 14614272Spst pgno_t pgno; 14714272Spst recno_t nextpg, prevpg; 14814272Spst int exact, level; 149189327Sdelphij 15014272Spst /* 15114272Spst * Find the first occurrence of the key in the tree. Toss the 15214272Spst * currently locked page so we don't hit an already-locked page. 15314272Spst */ 15414272Spst h = *hp; 15514272Spst mpool_put(t->bt_mp, h, 0); 15614272Spst if ((e = __bt_search(t, &c->key, &exact)) == NULL) 15714272Spst return (1); 15814272Spst h = e->page; 15914272Spst 16014272Spst /* See if we got it in one shot. */ 16114272Spst if (h->pgno == c->pg.pgno) 16214272Spst goto ret; 16314272Spst 16414272Spst /* 16514272Spst * Move right, looking for the page. At each move we have to move 16614272Spst * up the stack until we don't have to move to the next page. If 16714272Spst * we have to change pages at an internal level, we have to fix the 16814272Spst * stack back up. 16914272Spst */ 17014272Spst while (h->pgno != c->pg.pgno) { 17114272Spst if ((nextpg = h->nextpg) == P_INVALID) 17214272Spst break; 17314272Spst mpool_put(t->bt_mp, h, 0); 17414272Spst 17514272Spst /* Move up the stack. */ 17614272Spst for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 17714272Spst /* Get the parent page. */ 17814272Spst if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 17914272Spst return (1); 18014272Spst 18114272Spst /* Move to the next index. */ 18214272Spst if (parent->index != NEXTINDEX(h) - 1) { 183189292Sdelphij idx = parent->index + 1; 184189292Sdelphij BT_PUSH(t, h->pgno, idx); 18514272Spst break; 18614272Spst } 18714272Spst mpool_put(t->bt_mp, h, 0); 18814272Spst } 18914272Spst 19014272Spst /* Restore the stack. */ 19114272Spst while (level--) { 19214272Spst /* Push the next level down onto the stack. */ 193189292Sdelphij bi = GETBINTERNAL(h, idx); 19414272Spst pgno = bi->pgno; 19514272Spst BT_PUSH(t, pgno, 0); 19614272Spst 19714272Spst /* Lose the currently pinned page. */ 19814272Spst mpool_put(t->bt_mp, h, 0); 19914272Spst 20014272Spst /* Get the next level down. */ 20114272Spst if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 20214272Spst return (1); 203189292Sdelphij idx = 0; 20414272Spst } 20514272Spst mpool_put(t->bt_mp, h, 0); 20614272Spst if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL) 20714272Spst return (1); 20814272Spst } 20914272Spst 21014272Spst if (h->pgno == c->pg.pgno) 21114272Spst goto ret; 21214272Spst 21314272Spst /* Reacquire the original stack. */ 21414272Spst mpool_put(t->bt_mp, h, 0); 21514272Spst if ((e = __bt_search(t, &c->key, &exact)) == NULL) 21614272Spst return (1); 21714272Spst h = e->page; 21814272Spst 21914272Spst /* 22014272Spst * Move left, looking for the page. At each move we have to move 22114272Spst * up the stack until we don't have to change pages to move to the 22214272Spst * next page. If we have to change pages at an internal level, we 22314272Spst * have to fix the stack back up. 22414272Spst */ 22514272Spst while (h->pgno != c->pg.pgno) { 22614272Spst if ((prevpg = h->prevpg) == P_INVALID) 22714272Spst break; 22814272Spst mpool_put(t->bt_mp, h, 0); 22914272Spst 23014272Spst /* Move up the stack. */ 23114272Spst for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 23214272Spst /* Get the parent page. */ 23314272Spst if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 23414272Spst return (1); 23514272Spst 23614272Spst /* Move to the next index. */ 23714272Spst if (parent->index != 0) { 238189292Sdelphij idx = parent->index - 1; 239189292Sdelphij BT_PUSH(t, h->pgno, idx); 24014272Spst break; 24114272Spst } 24214272Spst mpool_put(t->bt_mp, h, 0); 24314272Spst } 24414272Spst 24514272Spst /* Restore the stack. */ 24614272Spst while (level--) { 24714272Spst /* Push the next level down onto the stack. */ 248189292Sdelphij bi = GETBINTERNAL(h, idx); 24914272Spst pgno = bi->pgno; 25014272Spst 25114272Spst /* Lose the currently pinned page. */ 25214272Spst mpool_put(t->bt_mp, h, 0); 25314272Spst 25414272Spst /* Get the next level down. */ 25514272Spst if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 25614272Spst return (1); 25714272Spst 258189292Sdelphij idx = NEXTINDEX(h) - 1; 259189292Sdelphij BT_PUSH(t, pgno, idx); 26014272Spst } 26114272Spst mpool_put(t->bt_mp, h, 0); 26214272Spst if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL) 26314272Spst return (1); 26414272Spst } 26514272Spst 266189327Sdelphij 26714272Spstret: mpool_put(t->bt_mp, h, 0); 26814272Spst return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL); 26914272Spst} 27014272Spst 27114272Spst/* 27214272Spst * __bt_bdelete -- 27314272Spst * Delete all key/data pairs matching the specified key. 27414272Spst * 27514272Spst * Parameters: 27614272Spst * t: tree 2771573Srgrimes * key: key to delete 2781573Srgrimes * 2791573Srgrimes * Returns: 2801573Srgrimes * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 2811573Srgrimes */ 2821573Srgrimesstatic int 283189291Sdelphij__bt_bdelete(BTREE *t, const DBT *key) 2841573Srgrimes{ 28514272Spst EPG *e; 2861573Srgrimes PAGE *h; 28714272Spst int deleted, exact, redo; 2881573Srgrimes 28914272Spst deleted = 0; 29014272Spst 2911573Srgrimes /* Find any matching record; __bt_search pins the page. */ 29214272Spstloop: if ((e = __bt_search(t, key, &exact)) == NULL) 29314272Spst return (deleted ? RET_SUCCESS : RET_ERROR); 2941573Srgrimes if (!exact) { 2951573Srgrimes mpool_put(t->bt_mp, e->page, 0); 29614272Spst return (deleted ? RET_SUCCESS : RET_SPECIAL); 2971573Srgrimes } 2981573Srgrimes 2991573Srgrimes /* 30014272Spst * Delete forward, then delete backward, from the found key. If 30114272Spst * there are duplicates and we reach either side of the page, do 30214272Spst * the key search again, so that we get them all. 3031573Srgrimes */ 30414272Spst redo = 0; 30514272Spst h = e->page; 30614272Spst do { 30714272Spst if (__bt_dleaf(t, key, h, e->index)) { 30814272Spst mpool_put(t->bt_mp, h, 0); 30914272Spst return (RET_ERROR); 31014272Spst } 31114272Spst if (F_ISSET(t, B_NODUPS)) { 31214272Spst if (NEXTINDEX(h) == 0) { 31314272Spst if (__bt_pdelete(t, h)) 3141573Srgrimes return (RET_ERROR); 31514272Spst } else 31614272Spst mpool_put(t->bt_mp, h, MPOOL_DIRTY); 31714272Spst return (RET_SUCCESS); 3181573Srgrimes } 31914272Spst deleted = 1; 32014272Spst } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); 3211573Srgrimes 32214272Spst /* Check for right-hand edge of the page. */ 32314272Spst if (e->index == NEXTINDEX(h)) 32414272Spst redo = 1; 32514272Spst 32614272Spst /* Delete from the key to the beginning of the page. */ 32714272Spst while (e->index-- > 0) { 3281573Srgrimes if (__bt_cmp(t, key, e) != 0) 3291573Srgrimes break; 33014272Spst if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) { 33114272Spst mpool_put(t->bt_mp, h, 0); 33214272Spst return (RET_ERROR); 33314272Spst } 33414272Spst if (e->index == 0) 33514272Spst redo = 1; 3361573Srgrimes } 3371573Srgrimes 33814272Spst /* Check for an empty page. */ 33914272Spst if (NEXTINDEX(h) == 0) { 34014272Spst if (__bt_pdelete(t, h)) 34114272Spst return (RET_ERROR); 34214272Spst goto loop; 34314272Spst } 34414272Spst 34514272Spst /* Put the page. */ 34614272Spst mpool_put(t->bt_mp, h, MPOOL_DIRTY); 34714272Spst 34814272Spst if (redo) 34914272Spst goto loop; 35014272Spst return (RET_SUCCESS); 35114272Spst} 35214272Spst 35314272Spst/* 35414272Spst * __bt_pdelete -- 35514272Spst * Delete a single page from the tree. 35614272Spst * 35714272Spst * Parameters: 35814272Spst * t: tree 35914272Spst * h: leaf page 36014272Spst * 36114272Spst * Returns: 36214272Spst * RET_SUCCESS, RET_ERROR. 36314272Spst * 36414272Spst * Side-effects: 36514272Spst * mpool_put's the page 36614272Spst */ 36714272Spststatic int 368189291Sdelphij__bt_pdelete(BTREE *t, PAGE *h) 36914272Spst{ 37014272Spst BINTERNAL *bi; 37114272Spst PAGE *pg; 37214272Spst EPGNO *parent; 373189292Sdelphij indx_t cnt, idx, *ip, offset; 37414272Spst u_int32_t nksize; 37514272Spst char *from; 37614272Spst 3771573Srgrimes /* 37814272Spst * Walk the parent page stack -- a LIFO stack of the pages that were 37914272Spst * traversed when we searched for the page where the delete occurred. 38014272Spst * Each stack entry is a page number and a page index offset. The 38114272Spst * offset is for the page traversed on the search. We've just deleted 38214272Spst * a page, so we have to delete the key from the parent page. 38314272Spst * 38414272Spst * If the delete from the parent page makes it empty, this process may 38514272Spst * continue all the way up the tree. We stop if we reach the root page 38614272Spst * (which is never deleted, it's just not worth the effort) or if the 38714272Spst * delete does not empty the page. 3881573Srgrimes */ 38914272Spst while ((parent = BT_POP(t)) != NULL) { 39014272Spst /* Get the parent page. */ 39114272Spst if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 39214272Spst return (RET_ERROR); 393189327Sdelphij 394189292Sdelphij idx = parent->index; 395189292Sdelphij bi = GETBINTERNAL(pg, idx); 3961573Srgrimes 39714272Spst /* Free any overflow pages. */ 39814272Spst if (bi->flags & P_BIGKEY && 39914272Spst __ovfl_delete(t, bi->bytes) == RET_ERROR) { 40014272Spst mpool_put(t->bt_mp, pg, 0); 40114272Spst return (RET_ERROR); 40214272Spst } 40314272Spst 40414272Spst /* 40514272Spst * Free the parent if it has only the one key and it's not the 40614272Spst * root page. If it's the rootpage, turn it back into an empty 40714272Spst * leaf page. 40814272Spst */ 409189327Sdelphij if (NEXTINDEX(pg) == 1) { 41014272Spst if (pg->pgno == P_ROOT) { 41114272Spst pg->lower = BTDATAOFF; 41214272Spst pg->upper = t->bt_psize; 41314272Spst pg->flags = P_BLEAF; 4141573Srgrimes } else { 41514272Spst if (__bt_relink(t, pg) || __bt_free(t, pg)) 4161573Srgrimes return (RET_ERROR); 41714272Spst continue; 4181573Srgrimes } 419189327Sdelphij } else { 42014272Spst /* Pack remaining key items at the end of the page. */ 42114272Spst nksize = NBINTERNAL(bi->ksize); 42214272Spst from = (char *)pg + pg->upper; 42314272Spst memmove(from + nksize, from, (char *)bi - from); 42414272Spst pg->upper += nksize; 42514272Spst 42614272Spst /* Adjust indices' offsets, shift the indices down. */ 427189292Sdelphij offset = pg->linp[idx]; 428189292Sdelphij for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip) 42914272Spst if (ip[0] < offset) 43014272Spst ip[0] += nksize; 431189292Sdelphij for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip) 43214272Spst ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1]; 43314272Spst pg->lower -= sizeof(indx_t); 4341573Srgrimes } 4351573Srgrimes 43614272Spst mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 43714272Spst break; 4381573Srgrimes } 4391573Srgrimes 44014272Spst /* Free the leaf page, as long as it wasn't the root. */ 44114272Spst if (h->pgno == P_ROOT) { 44214272Spst mpool_put(t->bt_mp, h, MPOOL_DIRTY); 44314272Spst return (RET_SUCCESS); 44414272Spst } 44514272Spst return (__bt_relink(t, h) || __bt_free(t, h)); 4461573Srgrimes} 4471573Srgrimes 4481573Srgrimes/* 44914272Spst * __bt_dleaf -- 45014272Spst * Delete a single record from a leaf page. 4511573Srgrimes * 4521573Srgrimes * Parameters: 4531573Srgrimes * t: tree 45414272Spst * key: referenced key 45514272Spst * h: page 456189292Sdelphij * idx: index on page to delete 4571573Srgrimes * 4581573Srgrimes * Returns: 4591573Srgrimes * RET_SUCCESS, RET_ERROR. 4601573Srgrimes */ 4611573Srgrimesint 462189292Sdelphij__bt_dleaf(BTREE *t, const DBT *key, PAGE *h, u_int idx) 4631573Srgrimes{ 46414272Spst BLEAF *bl; 46514272Spst indx_t cnt, *ip, offset; 46614272Spst u_int32_t nbytes; 46714272Spst void *to; 4681573Srgrimes char *from; 4691573Srgrimes 47014272Spst /* If this record is referenced by the cursor, delete the cursor. */ 47114272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 47214272Spst !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 473189292Sdelphij t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx && 474189292Sdelphij __bt_curdel(t, key, h, idx)) 47514272Spst return (RET_ERROR); 47614272Spst 47714272Spst /* If the entry uses overflow pages, make them available for reuse. */ 478189292Sdelphij to = bl = GETBLEAF(h, idx); 4791573Srgrimes if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) 4801573Srgrimes return (RET_ERROR); 4811573Srgrimes if (bl->flags & P_BIGDATA && 4821573Srgrimes __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) 4831573Srgrimes return (RET_ERROR); 48414272Spst 48514272Spst /* Pack the remaining key/data items at the end of the page. */ 4861573Srgrimes nbytes = NBLEAF(bl); 4871573Srgrimes from = (char *)h + h->upper; 4881573Srgrimes memmove(from + nbytes, from, (char *)to - from); 4891573Srgrimes h->upper += nbytes; 4901573Srgrimes 49114272Spst /* Adjust the indices' offsets, shift the indices down. */ 492189292Sdelphij offset = h->linp[idx]; 493189292Sdelphij for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip) 4941573Srgrimes if (ip[0] < offset) 4951573Srgrimes ip[0] += nbytes; 496189292Sdelphij for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip) 4971573Srgrimes ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 4981573Srgrimes h->lower -= sizeof(indx_t); 49914272Spst 50014272Spst /* If the cursor is on this page, adjust it as necessary. */ 50114272Spst if (F_ISSET(&t->bt_cursor, CURS_INIT) && 50214272Spst !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 503189292Sdelphij t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx) 50414272Spst --t->bt_cursor.pg.index; 50514272Spst 5061573Srgrimes return (RET_SUCCESS); 5071573Srgrimes} 50814272Spst 50914272Spst/* 51014272Spst * __bt_curdel -- 51114272Spst * Delete the cursor. 51214272Spst * 51314272Spst * Parameters: 51414272Spst * t: tree 51514272Spst * key: referenced key (or NULL) 51614272Spst * h: page 517189292Sdelphij * idx: index on page to delete 51814272Spst * 51914272Spst * Returns: 52014272Spst * RET_SUCCESS, RET_ERROR. 52114272Spst */ 52214272Spststatic int 523189292Sdelphij__bt_curdel(BTREE *t, const DBT *key, PAGE *h, u_int idx) 52414272Spst{ 52514272Spst CURSOR *c; 52614272Spst EPG e; 52714272Spst PAGE *pg; 52814272Spst int curcopy, status; 52914272Spst 53014272Spst /* 53114272Spst * If there are duplicates, move forward or backward to one. 53214272Spst * Otherwise, copy the key into the cursor area. 53314272Spst */ 53414272Spst c = &t->bt_cursor; 53514272Spst F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE); 53614272Spst 53714272Spst curcopy = 0; 53814272Spst if (!F_ISSET(t, B_NODUPS)) { 53914272Spst /* 54014272Spst * We're going to have to do comparisons. If we weren't 54114272Spst * provided a copy of the key, i.e. the user is deleting 54214272Spst * the current cursor position, get one. 54314272Spst */ 54414272Spst if (key == NULL) { 54514272Spst e.page = h; 546189292Sdelphij e.index = idx; 54714272Spst if ((status = __bt_ret(t, &e, 54814272Spst &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS) 54914272Spst return (status); 55014272Spst curcopy = 1; 55114272Spst key = &c->key; 55214272Spst } 55314272Spst /* Check previous key, if not at the beginning of the page. */ 554189327Sdelphij if (idx > 0) { 55514272Spst e.page = h; 556189292Sdelphij e.index = idx - 1; 55714272Spst if (__bt_cmp(t, key, &e) == 0) { 55814272Spst F_SET(c, CURS_BEFORE); 55914272Spst goto dup2; 56014272Spst } 56114272Spst } 56214272Spst /* Check next key, if not at the end of the page. */ 563189292Sdelphij if (idx < NEXTINDEX(h) - 1) { 56414272Spst e.page = h; 565189292Sdelphij e.index = idx + 1; 56614272Spst if (__bt_cmp(t, key, &e) == 0) { 56714272Spst F_SET(c, CURS_AFTER); 56814272Spst goto dup2; 56914272Spst } 57014272Spst } 57114272Spst /* Check previous key if at the beginning of the page. */ 572189292Sdelphij if (idx == 0 && h->prevpg != P_INVALID) { 57314272Spst if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) 57414272Spst return (RET_ERROR); 57514272Spst e.page = pg; 57614272Spst e.index = NEXTINDEX(pg) - 1; 57714272Spst if (__bt_cmp(t, key, &e) == 0) { 57814272Spst F_SET(c, CURS_BEFORE); 57914272Spst goto dup1; 58014272Spst } 58114272Spst mpool_put(t->bt_mp, pg, 0); 58214272Spst } 58314272Spst /* Check next key if at the end of the page. */ 584189292Sdelphij if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) { 58514272Spst if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) 58614272Spst return (RET_ERROR); 58714272Spst e.page = pg; 58814272Spst e.index = 0; 58914272Spst if (__bt_cmp(t, key, &e) == 0) { 59014272Spst F_SET(c, CURS_AFTER); 59114272Spstdup1: mpool_put(t->bt_mp, pg, 0); 59214272Spstdup2: c->pg.pgno = e.page->pgno; 59314272Spst c->pg.index = e.index; 59414272Spst return (RET_SUCCESS); 59514272Spst } 59614272Spst mpool_put(t->bt_mp, pg, 0); 59714272Spst } 59814272Spst } 59914272Spst e.page = h; 600189292Sdelphij e.index = idx; 60114272Spst if (curcopy || (status = 60214272Spst __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) { 60314272Spst F_SET(c, CURS_ACQUIRE); 60414272Spst return (RET_SUCCESS); 60514272Spst } 60614272Spst return (status); 60714272Spst} 60814272Spst 60914272Spst/* 61014272Spst * __bt_relink -- 61114272Spst * Link around a deleted page. 61214272Spst * 61314272Spst * Parameters: 61414272Spst * t: tree 61514272Spst * h: page to be deleted 61614272Spst */ 61714272Spststatic int 618189291Sdelphij__bt_relink(BTREE *t, PAGE *h) 61914272Spst{ 62014272Spst PAGE *pg; 62114272Spst 62214272Spst if (h->nextpg != P_INVALID) { 62314272Spst if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) 62414272Spst return (RET_ERROR); 62514272Spst pg->prevpg = h->prevpg; 62614272Spst mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 62714272Spst } 62814272Spst if (h->prevpg != P_INVALID) { 62914272Spst if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) 63014272Spst return (RET_ERROR); 63114272Spst pg->nextpg = h->nextpg; 63214272Spst mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 63314272Spst } 63414272Spst return (0); 63514272Spst} 636