aboutsummaryrefslogtreecommitdiffstats
path: root/trunk/main/db1-ast/btree/bt_delete.c
diff options
context:
space:
mode:
Diffstat (limited to 'trunk/main/db1-ast/btree/bt_delete.c')
-rw-r--r--trunk/main/db1-ast/btree/bt_delete.c657
1 files changed, 0 insertions, 657 deletions
diff --git a/trunk/main/db1-ast/btree/bt_delete.c b/trunk/main/db1-ast/btree/bt_delete.c
deleted file mode 100644
index e816c432a..000000000
--- a/trunk/main/db1-ast/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 "../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 = 0;
- 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);
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-23 19:25:46 +0000