diff options
Diffstat (limited to 'db/btree/bt_delete.c')
| -rw-r--r-- | db/btree/bt_delete.c | 657 |
1 files changed, 0 insertions, 657 deletions
diff --git a/db/btree/bt_delete.c b/db/btree/bt_delete.c deleted file mode 100644 index b654c9f1f8..0000000000 --- a/db/btree/bt_delete.c +++ /dev/null @@ -1,657 +0,0 @@ -/*- - * Copyright (c) 1990, 1993, 1994 - * The Regents of the University of California. All rights reserved. - * - * This code is derived from software contributed to Berkeley by - * Mike Olson. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -#if defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94"; -#endif /* LIBC_SCCS and not lint */ - -#include <sys/types.h> - -#include <errno.h> -#include <stdio.h> -#include <string.h> - -#include <db.h> -#include "btree.h" - -static int __bt_bdelete __P((BTREE *, const DBT *)); -static int __bt_curdel __P((BTREE *, const DBT *, PAGE *, u_int)); -static int __bt_pdelete __P((BTREE *, PAGE *)); -static int __bt_relink __P((BTREE *, PAGE *)); -static int __bt_stkacq __P((BTREE *, PAGE **, CURSOR *)); - -/* - * __bt_delete - * Delete the item(s) referenced by a key. - * - * Return RET_SPECIAL if the key is not found. - */ -int -__bt_delete(dbp, key, flags) - const DB *dbp; - const DBT *key; - u_int flags; -{ - BTREE *t; - CURSOR *c; - PAGE *h; - int status; - - t = dbp->internal; - - /* Toss any page pinned across calls. */ - if (t->bt_pinned != NULL) { - mpool_put(t->bt_mp, t->bt_pinned, 0); - t->bt_pinned = NULL; - } - - /* Check for change to a read-only tree. */ - if (F_ISSET(t, B_RDONLY)) { - errno = EPERM; - return (RET_ERROR); - } - - switch (flags) { - case 0: - status = __bt_bdelete(t, key); - break; - case R_CURSOR: - /* - * If flags is R_CURSOR, delete the cursor. Must already - * have started a scan and not have already deleted it. - */ - c = &t->bt_cursor; - if (F_ISSET(c, CURS_INIT)) { - if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) - return (RET_SPECIAL); - if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) - return (RET_ERROR); - - /* - * If the page is about to be emptied, we'll need to - * delete it, which means we have to acquire a stack. - */ - if (NEXTINDEX(h) == 1) - if (__bt_stkacq(t, &h, &t->bt_cursor)) - return (RET_ERROR); - - status = __bt_dleaf(t, NULL, h, c->pg.index); - - if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) { - if (__bt_pdelete(t, h)) - return (RET_ERROR); - } else - mpool_put(t->bt_mp, - h, status == RET_SUCCESS ? MPOOL_DIRTY : 0); - break; - } - /* FALLTHROUGH */ - default: - errno = EINVAL; - return (RET_ERROR); - } - if (status == RET_SUCCESS) - F_SET(t, B_MODIFIED); - return (status); -} - -/* - * __bt_stkacq -- - * Acquire a stack so we can delete a cursor entry. - * - * Parameters: - * t: tree - * hp: pointer to current, pinned PAGE pointer - * c: pointer to the cursor - * - * Returns: - * 0 on success, 1 on failure - */ -static int -__bt_stkacq(t, hp, c) - BTREE *t; - PAGE **hp; - CURSOR *c; -{ - BINTERNAL *bi; - EPG *e; - EPGNO *parent; - PAGE *h; - indx_t index; - pgno_t pgno; - recno_t nextpg, prevpg; - int exact, level; - - /* - * Find the first occurrence of the key in the tree. Toss the - * currently locked page so we don't hit an already-locked page. - */ - h = *hp; - mpool_put(t->bt_mp, h, 0); - if ((e = __bt_search(t, &c->key, &exact)) == NULL) - return (1); - h = e->page; - - /* See if we got it in one shot. */ - if (h->pgno == c->pg.pgno) - goto ret; - - /* - * Move right, looking for the page. At each move we have to move - * up the stack until we don't have to move to the next page. If - * we have to change pages at an internal level, we have to fix the - * stack back up. - */ - while (h->pgno != c->pg.pgno) { - if ((nextpg = h->nextpg) == P_INVALID) - break; - mpool_put(t->bt_mp, h, 0); - - /* Move up the stack. */ - for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { - /* Get the parent page. */ - if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) - return (1); - - /* Move to the next index. */ - if (parent->index != NEXTINDEX(h) - 1) { - index = parent->index + 1; - BT_PUSH(t, h->pgno, index); - break; - } - mpool_put(t->bt_mp, h, 0); - } - - /* Restore the stack. */ - while (level--) { - /* Push the next level down onto the stack. */ - bi = GETBINTERNAL(h, index); - pgno = bi->pgno; - BT_PUSH(t, pgno, 0); - - /* Lose the currently pinned page. */ - mpool_put(t->bt_mp, h, 0); - - /* Get the next level down. */ - if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) - return (1); - index = 0; - } - mpool_put(t->bt_mp, h, 0); - if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL) - return (1); - } - - if (h->pgno == c->pg.pgno) - goto ret; - - /* Reacquire the original stack. */ - mpool_put(t->bt_mp, h, 0); - if ((e = __bt_search(t, &c->key, &exact)) == NULL) - return (1); - h = e->page; - - /* - * Move left, looking for the page. At each move we have to move - * up the stack until we don't have to change pages to move to the - * next page. If we have to change pages at an internal level, we - * have to fix the stack back up. - */ - while (h->pgno != c->pg.pgno) { - if ((prevpg = h->prevpg) == P_INVALID) - break; - mpool_put(t->bt_mp, h, 0); - - /* Move up the stack. */ - for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { - /* Get the parent page. */ - if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) - return (1); - - /* Move to the next index. */ - if (parent->index != 0) { - index = parent->index - 1; - BT_PUSH(t, h->pgno, index); - break; - } - mpool_put(t->bt_mp, h, 0); - } - - /* Restore the stack. */ - while (level--) { - /* Push the next level down onto the stack. */ - bi = GETBINTERNAL(h, index); - pgno = bi->pgno; - - /* Lose the currently pinned page. */ - mpool_put(t->bt_mp, h, 0); - - /* Get the next level down. */ - if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) - return (1); - - index = NEXTINDEX(h) - 1; - BT_PUSH(t, pgno, index); - } - mpool_put(t->bt_mp, h, 0); - if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL) - return (1); - } - - -ret: mpool_put(t->bt_mp, h, 0); - return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL); -} - -/* - * __bt_bdelete -- - * Delete all key/data pairs matching the specified key. - * - * Parameters: - * t: tree - * key: key to delete - * - * Returns: - * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. - */ -static int -__bt_bdelete(t, key) - BTREE *t; - const DBT *key; -{ - EPG *e; - PAGE *h; - int deleted, exact, redo; - - deleted = 0; - - /* Find any matching record; __bt_search pins the page. */ -loop: if ((e = __bt_search(t, key, &exact)) == NULL) - return (deleted ? RET_SUCCESS : RET_ERROR); - if (!exact) { - mpool_put(t->bt_mp, e->page, 0); - return (deleted ? RET_SUCCESS : RET_SPECIAL); - } - - /* - * Delete forward, then delete backward, from the found key. If - * there are duplicates and we reach either side of the page, do - * the key search again, so that we get them all. - */ - redo = 0; - h = e->page; - do { - if (__bt_dleaf(t, key, h, e->index)) { - mpool_put(t->bt_mp, h, 0); - return (RET_ERROR); - } - if (F_ISSET(t, B_NODUPS)) { - if (NEXTINDEX(h) == 0) { - if (__bt_pdelete(t, h)) - return (RET_ERROR); - } else - mpool_put(t->bt_mp, h, MPOOL_DIRTY); - return (RET_SUCCESS); - } - deleted = 1; - } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); - - /* Check for right-hand edge of the page. */ - if (e->index == NEXTINDEX(h)) - redo = 1; - - /* Delete from the key to the beginning of the page. */ - while (e->index-- > 0) { - if (__bt_cmp(t, key, e) != 0) - break; - if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) { - mpool_put(t->bt_mp, h, 0); - return (RET_ERROR); - } - if (e->index == 0) - redo = 1; - } - - /* Check for an empty page. */ - if (NEXTINDEX(h) == 0) { - if (__bt_pdelete(t, h)) - return (RET_ERROR); - goto loop; - } - - /* Put the page. */ - mpool_put(t->bt_mp, h, MPOOL_DIRTY); - - if (redo) - goto loop; - return (RET_SUCCESS); -} - -/* - * __bt_pdelete -- - * Delete a single page from the tree. - * - * Parameters: - * t: tree - * h: leaf page - * - * Returns: - * RET_SUCCESS, RET_ERROR. - * - * Side-effects: - * mpool_put's the page - */ -static int -__bt_pdelete(t, h) - BTREE *t; - PAGE *h; -{ - BINTERNAL *bi; - PAGE *pg; - EPGNO *parent; - indx_t cnt, index, *ip, offset; - u_int32_t nksize; - char *from; - - /* - * Walk the parent page stack -- a LIFO stack of the pages that were - * traversed when we searched for the page where the delete occurred. - * Each stack entry is a page number and a page index offset. The - * offset is for the page traversed on the search. We've just deleted - * a page, so we have to delete the key from the parent page. - * - * If the delete from the parent page makes it empty, this process may - * continue all the way up the tree. We stop if we reach the root page - * (which is never deleted, it's just not worth the effort) or if the - * delete does not empty the page. - */ - while ((parent = BT_POP(t)) != NULL) { - /* Get the parent page. */ - if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) - return (RET_ERROR); - - index = parent->index; - bi = GETBINTERNAL(pg, index); - - /* Free any overflow pages. */ - if (bi->flags & P_BIGKEY && - __ovfl_delete(t, bi->bytes) == RET_ERROR) { - mpool_put(t->bt_mp, pg, 0); - return (RET_ERROR); - } - - /* - * Free the parent if it has only the one key and it's not the - * root page. If it's the rootpage, turn it back into an empty - * leaf page. - */ - if (NEXTINDEX(pg) == 1) { - if (pg->pgno == P_ROOT) { - pg->lower = BTDATAOFF; - pg->upper = t->bt_psize; - pg->flags = P_BLEAF; - } else { - if (__bt_relink(t, pg) || __bt_free(t, pg)) - return (RET_ERROR); - continue; - } - } else { - /* Pack remaining key items at the end of the page. */ - nksize = NBINTERNAL(bi->ksize); - from = (char *)pg + pg->upper; - memmove(from + nksize, from, (char *)bi - from); - pg->upper += nksize; - - /* Adjust indices' offsets, shift the indices down. */ - offset = pg->linp[index]; - for (cnt = index, ip = &pg->linp[0]; cnt--; ++ip) - if (ip[0] < offset) - ip[0] += nksize; - for (cnt = NEXTINDEX(pg) - index; --cnt; ++ip) - ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1]; - pg->lower -= sizeof(indx_t); - } - - mpool_put(t->bt_mp, pg, MPOOL_DIRTY); - break; - } - - /* Free the leaf page, as long as it wasn't the root. */ - if (h->pgno == P_ROOT) { - mpool_put(t->bt_mp, h, MPOOL_DIRTY); - return (RET_SUCCESS); - } - return (__bt_relink(t, h) || __bt_free(t, h)); -} - -/* - * __bt_dleaf -- - * Delete a single record from a leaf page. - * - * Parameters: - * t: tree - * key: referenced key - * h: page - * index: index on page to delete - * - * Returns: - * RET_SUCCESS, RET_ERROR. - */ -int -__bt_dleaf(t, key, h, index) - BTREE *t; - const DBT *key; - PAGE *h; - u_int index; -{ - BLEAF *bl; - indx_t cnt, *ip, offset; - u_int32_t nbytes; - void *to; - char *from; - - /* If this record is referenced by the cursor, delete the cursor. */ - if (F_ISSET(&t->bt_cursor, CURS_INIT) && - !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && - t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == index && - __bt_curdel(t, key, h, index)) - return (RET_ERROR); - - /* If the entry uses overflow pages, make them available for reuse. */ - to = bl = GETBLEAF(h, index); - if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) - return (RET_ERROR); - if (bl->flags & P_BIGDATA && - __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) - return (RET_ERROR); - - /* Pack the remaining key/data items at the end of the page. */ - nbytes = NBLEAF(bl); - from = (char *)h + h->upper; - memmove(from + nbytes, from, (char *)to - from); - h->upper += nbytes; - - /* Adjust the indices' offsets, shift the indices down. */ - offset = h->linp[index]; - for (cnt = index, ip = &h->linp[0]; cnt--; ++ip) - if (ip[0] < offset) - ip[0] += nbytes; - for (cnt = NEXTINDEX(h) - index; --cnt; ++ip) - ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; - h->lower -= sizeof(indx_t); - - /* If the cursor is on this page, adjust it as necessary. */ - if (F_ISSET(&t->bt_cursor, CURS_INIT) && - !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && - t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > index) - --t->bt_cursor.pg.index; - - return (RET_SUCCESS); -} - -/* - * __bt_curdel -- - * Delete the cursor. - * - * Parameters: - * t: tree - * key: referenced key (or NULL) - * h: page - * index: index on page to delete - * - * Returns: - * RET_SUCCESS, RET_ERROR. - */ -static int -__bt_curdel(t, key, h, index) - BTREE *t; - const DBT *key; - PAGE *h; - u_int index; -{ - CURSOR *c; - EPG e; - PAGE *pg; - int curcopy, status; - - /* - * If there are duplicates, move forward or backward to one. - * Otherwise, copy the key into the cursor area. - */ - c = &t->bt_cursor; - F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE); - - curcopy = 0; - if (!F_ISSET(t, B_NODUPS)) { - /* - * We're going to have to do comparisons. If we weren't - * provided a copy of the key, i.e. the user is deleting - * the current cursor position, get one. - */ - if (key == NULL) { - e.page = h; - e.index = index; - if ((status = __bt_ret(t, &e, - &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS) - return (status); - curcopy = 1; - key = &c->key; - } - /* Check previous key, if not at the beginning of the page. */ - if (index > 0) { - e.page = h; - e.index = index - 1; - if (__bt_cmp(t, key, &e) == 0) { - F_SET(c, CURS_BEFORE); - goto dup2; - } - } - /* Check next key, if not at the end of the page. */ - if (index < NEXTINDEX(h) - 1) { - e.page = h; - e.index = index + 1; - if (__bt_cmp(t, key, &e) == 0) { - F_SET(c, CURS_AFTER); - goto dup2; - } - } - /* Check previous key if at the beginning of the page. */ - if (index == 0 && h->prevpg != P_INVALID) { - if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) - return (RET_ERROR); - e.page = pg; - e.index = NEXTINDEX(pg) - 1; - if (__bt_cmp(t, key, &e) == 0) { - F_SET(c, CURS_BEFORE); - goto dup1; - } - mpool_put(t->bt_mp, pg, 0); - } - /* Check next key if at the end of the page. */ - if (index == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) { - if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) - return (RET_ERROR); - e.page = pg; - e.index = 0; - if (__bt_cmp(t, key, &e) == 0) { - F_SET(c, CURS_AFTER); -dup1: mpool_put(t->bt_mp, pg, 0); -dup2: c->pg.pgno = e.page->pgno; - c->pg.index = e.index; - return (RET_SUCCESS); - } - mpool_put(t->bt_mp, pg, 0); - } - } - e.page = h; - e.index = index; - if (curcopy || (status = - __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) { - F_SET(c, CURS_ACQUIRE); - return (RET_SUCCESS); - } - return (status); -} - -/* - * __bt_relink -- - * Link around a deleted page. - * - * Parameters: - * t: tree - * h: page to be deleted - */ -static int -__bt_relink(t, h) - BTREE *t; - PAGE *h; -{ - PAGE *pg; - - if (h->nextpg != P_INVALID) { - if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) - return (RET_ERROR); - pg->prevpg = h->prevpg; - mpool_put(t->bt_mp, pg, MPOOL_DIRTY); - } - if (h->prevpg != P_INVALID) { - if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) - return (RET_ERROR); - pg->nextpg = h->nextpg; - mpool_put(t->bt_mp, pg, MPOOL_DIRTY); - } - return (0); -} |