[apple/libc.git] / db / btree / FreeBSD / bt_delete.c

/*-
 * 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.
 * 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/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/db/btree/bt_delete.c,v 1.6 2009/03/04 00:58:04 delphij Exp $");

#include <sys/types.h>

#include <errno.h>
#include <stdio.h>
#include <string.h>

#include <db.h>
#include "btree.h"

static int __bt_bdelete(BTREE *, const DBT *);
static int __bt_curdel(BTREE *, const DBT *, PAGE *, u_int);
static int __bt_pdelete(BTREE *, PAGE *);
static int __bt_relink(BTREE *, PAGE *);
static int __bt_stkacq(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(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(BTREE *t, PAGE **hp, CURSOR *c)
{
	BINTERNAL *bi;
	EPG *e;
	EPGNO *parent;
	PAGE *h;
	indx_t idx;
	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) {
				idx = parent->index + 1;
				BT_PUSH(t, h->pgno, idx);
				break;
			}
			mpool_put(t->bt_mp, h, 0);
		}

		/* Restore the stack. */
		while (level--) {
			/* Push the next level down onto the stack. */
			bi = GETBINTERNAL(h, idx);
			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);
			idx = 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) {
				idx = parent->index - 1;
				BT_PUSH(t, h->pgno, idx);
				break;
			}
			mpool_put(t->bt_mp, h, 0);
		}

		/* Restore the stack. */
		while (level--) {
			/* Push the next level down onto the stack. */
			bi = GETBINTERNAL(h, idx);
			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);

			idx = NEXTINDEX(h) - 1;
			BT_PUSH(t, pgno, idx);
		}
		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(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(BTREE *t, PAGE *h)
{
	BINTERNAL *bi;
	PAGE *pg;
	EPGNO *parent;
	indx_t cnt, idx, *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);

		idx = parent->index;
		bi = GETBINTERNAL(pg, idx);

		/* 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[idx];
			for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip)
				if (ip[0] < offset)
					ip[0] += nksize;
			for (cnt = NEXTINDEX(pg) - idx; --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
 *	idx:	index on page to delete
 *
 * Returns:
 *	RET_SUCCESS, RET_ERROR.
 */
int
__bt_dleaf(BTREE *t, const DBT *key, PAGE *h, u_int idx)
{
	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 == idx &&
	    __bt_curdel(t, key, h, idx))
		return (RET_ERROR);

	/* If the entry uses overflow pages, make them available for reuse. */
	to = bl = GETBLEAF(h, idx);
	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[idx];
	for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip)
		if (ip[0] < offset)
			ip[0] += nbytes;
	for (cnt = NEXTINDEX(h) - idx; --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 > idx)
		--t->bt_cursor.pg.index;

	return (RET_SUCCESS);
}

/*
 * __bt_curdel --
 *	Delete the cursor.
 *
 * Parameters:
 *	t:	tree
 *    key:	referenced key (or NULL)
 *	h:	page
 *    idx:	index on page to delete
 *
 * Returns:
 *	RET_SUCCESS, RET_ERROR.
 */
static int
__bt_curdel(BTREE *t, const DBT *key, PAGE *h, u_int idx)
{
	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 = idx;
			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 (idx > 0) {
			e.page = h;
			e.index = idx - 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 (idx < NEXTINDEX(h) - 1) {
			e.page = h;
			e.index = idx + 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 (idx == 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 (idx == 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 = idx;
	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(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);
}
Commit	Line	Data
9385eb3d A	1	/*-
9385eb3d A	2	* Copyright (c) 1990, 1993, 1994
e9ce8d39 A	3	* The Regents of the University of California. All rights reserved.
	4	*
	5	* This code is derived from software contributed to Berkeley by
	6	* Mike Olson.
	7	*
	8	* Redistribution and use in source and binary forms, with or without
	9	* modification, are permitted provided that the following conditions
	10	* are met:
	11	* 1. Redistributions of source code must retain the above copyright
	12	* notice, this list of conditions and the following disclaimer.
	13	* 2. Redistributions in binary form must reproduce the above copyright
	14	* notice, this list of conditions and the following disclaimer in the
	15	* documentation and/or other materials provided with the distribution.
e9ce8d39 A	16	* 4. Neither the name of the University nor the names of its contributors
	17	* may be used to endorse or promote products derived from this software
	18	* without specific prior written permission.
	19	*
	20	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	21	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	22	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	23	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	24	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	25	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	26	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	27	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	28	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	29	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	30	* SUCH DAMAGE.
	31	*/
	32
9385eb3d A	33	#if defined(LIBC_SCCS) && !defined(lint)
	34	static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94";
	35	#endif /* LIBC_SCCS and not lint */
	36	#include <sys/cdefs.h>
1f2f436a	37	__FBSDID("$FreeBSD: src/lib/libc/db/btree/bt_delete.c,v 1.6 2009/03/04 00:58:04 delphij Exp $");
e9ce8d39 A	38
	39	#include <sys/types.h>
	40
	41	#include <errno.h>
	42	#include <stdio.h>
	43	#include <string.h>
	44
	45	#include <db.h>
	46	#include "btree.h"
	47
9385eb3d A	48	static int __bt_bdelete(BTREE , const DBT );
	49	static int __bt_curdel(BTREE , const DBT , PAGE *, u_int);
	50	static int __bt_pdelete(BTREE , PAGE );
	51	static int __bt_relink(BTREE , PAGE );
	52	static int __bt_stkacq(BTREE , PAGE , CURSOR );
e9ce8d39 A	53
e9ce8d39 A	54	/*
9385eb3d A	55	* __bt_delete
9385eb3d A	56	* Delete the item(s) referenced by a key.
e9ce8d39	57	*
9385eb3d	58	* Return RET_SPECIAL if the key is not found.
e9ce8d39 A	59	*/
e9ce8d39 A	60	int
1f2f436a	61	__bt_delete(const DB dbp, const DBT key, u_int flags)
e9ce8d39 A	62	{
e9ce8d39 A	63	BTREE *t;
9385eb3d A	64	CURSOR *c;
9385eb3d A	65	PAGE *h;
e9ce8d39 A	66	int status;
	67
	68	t = dbp->internal;
	69
	70	/* Toss any page pinned across calls. */
	71	if (t->bt_pinned != NULL) {
	72	mpool_put(t->bt_mp, t->bt_pinned, 0);
	73	t->bt_pinned = NULL;
	74	}
	75
9385eb3d A	76	/* Check for change to a read-only tree. */
9385eb3d A	77	if (F_ISSET(t, B_RDONLY)) {
e9ce8d39 A	78	errno = EPERM;
	79	return (RET_ERROR);
	80	}
	81
9385eb3d	82	switch (flags) {
e9ce8d39	83	case 0:
9385eb3d	84	status = __bt_bdelete(t, key);
e9ce8d39 A	85	break;
	86	case R_CURSOR:
	87	/*
9385eb3d A	88	* If flags is R_CURSOR, delete the cursor. Must already
9385eb3d A	89	* have started a scan and not have already deleted it.
e9ce8d39	90	*/
9385eb3d A	91	c = &t->bt_cursor;
	92	if (F_ISSET(c, CURS_INIT)) {
	93	if (F_ISSET(c, CURS_ACQUIRE \| CURS_AFTER \| CURS_BEFORE))
	94	return (RET_SPECIAL);
	95	if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL)
	96	return (RET_ERROR);
	97
	98	/*
	99	* If the page is about to be emptied, we'll need to
	100	* delete it, which means we have to acquire a stack.
	101	*/
	102	if (NEXTINDEX(h) == 1)
	103	if (__bt_stkacq(t, &h, &t->bt_cursor))
	104	return (RET_ERROR);
	105
	106	status = __bt_dleaf(t, NULL, h, c->pg.index);
	107
	108	if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) {
	109	if (__bt_pdelete(t, h))
	110	return (RET_ERROR);
	111	} else
	112	mpool_put(t->bt_mp,
	113	h, status == RET_SUCCESS ? MPOOL_DIRTY : 0);
	114	break;
	115	}
	116	/* FALLTHROUGH */
e9ce8d39	117	default:
9385eb3d	118	errno = EINVAL;
e9ce8d39 A	119	return (RET_ERROR);
	120	}
	121	if (status == RET_SUCCESS)
9385eb3d	122	F_SET(t, B_MODIFIED);
e9ce8d39 A	123	return (status);
	124	}
	125
	126	/*
9385eb3d A	127	* __bt_stkacq --
9385eb3d A	128	* Acquire a stack so we can delete a cursor entry.
e9ce8d39 A	129	*
e9ce8d39 A	130	* Parameters:
9385eb3d A	131	* t: tree
	132	* hp: pointer to current, pinned PAGE pointer
	133	* c: pointer to the cursor
	134	*
	135	* Returns:
	136	* 0 on success, 1 on failure
	137	*/
	138	static int
1f2f436a	139	__bt_stkacq(BTREE t, PAGE hp, CURSOR c)
9385eb3d A	140	{
	141	BINTERNAL *bi;
	142	EPG *e;
	143	EPGNO *parent;
	144	PAGE *h;
1f2f436a	145	indx_t idx;
9385eb3d A	146	pgno_t pgno;
	147	recno_t nextpg, prevpg;
	148	int exact, level;
1f2f436a	149
9385eb3d A	150	/*
	151	* Find the first occurrence of the key in the tree. Toss the
	152	* currently locked page so we don't hit an already-locked page.
	153	*/
	154	h = *hp;
	155	mpool_put(t->bt_mp, h, 0);
	156	if ((e = __bt_search(t, &c->key, &exact)) == NULL)
	157	return (1);
	158	h = e->page;
	159
	160	/* See if we got it in one shot. */
	161	if (h->pgno == c->pg.pgno)
	162	goto ret;
	163
	164	/*
	165	* Move right, looking for the page. At each move we have to move
	166	* up the stack until we don't have to move to the next page. If
	167	* we have to change pages at an internal level, we have to fix the
	168	* stack back up.
	169	*/
	170	while (h->pgno != c->pg.pgno) {
	171	if ((nextpg = h->nextpg) == P_INVALID)
	172	break;
	173	mpool_put(t->bt_mp, h, 0);
	174
	175	/* Move up the stack. */
	176	for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
	177	/* Get the parent page. */
	178	if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
	179	return (1);
	180
	181	/* Move to the next index. */
	182	if (parent->index != NEXTINDEX(h) - 1) {
1f2f436a A	183	idx = parent->index + 1;
1f2f436a A	184	BT_PUSH(t, h->pgno, idx);
9385eb3d A	185	break;
	186	}
	187	mpool_put(t->bt_mp, h, 0);
	188	}
	189
	190	/* Restore the stack. */
	191	while (level--) {
	192	/* Push the next level down onto the stack. */
1f2f436a	193	bi = GETBINTERNAL(h, idx);
9385eb3d A	194	pgno = bi->pgno;
	195	BT_PUSH(t, pgno, 0);
	196
	197	/* Lose the currently pinned page. */
	198	mpool_put(t->bt_mp, h, 0);
	199
	200	/* Get the next level down. */
	201	if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
	202	return (1);
1f2f436a	203	idx = 0;
9385eb3d A	204	}
	205	mpool_put(t->bt_mp, h, 0);
	206	if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL)
	207	return (1);
	208	}
	209
	210	if (h->pgno == c->pg.pgno)
	211	goto ret;
	212
	213	/* Reacquire the original stack. */
	214	mpool_put(t->bt_mp, h, 0);
	215	if ((e = __bt_search(t, &c->key, &exact)) == NULL)
	216	return (1);
	217	h = e->page;
	218
	219	/*
	220	* Move left, looking for the page. At each move we have to move
	221	* up the stack until we don't have to change pages to move to the
	222	* next page. If we have to change pages at an internal level, we
	223	* have to fix the stack back up.
	224	*/
	225	while (h->pgno != c->pg.pgno) {
	226	if ((prevpg = h->prevpg) == P_INVALID)
	227	break;
	228	mpool_put(t->bt_mp, h, 0);
	229
	230	/* Move up the stack. */
	231	for (level = 0; (parent = BT_POP(t)) != NULL; ++level) {
	232	/* Get the parent page. */
	233	if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
	234	return (1);
	235
	236	/* Move to the next index. */
	237	if (parent->index != 0) {
1f2f436a A	238	idx = parent->index - 1;
1f2f436a A	239	BT_PUSH(t, h->pgno, idx);
9385eb3d A	240	break;
	241	}
	242	mpool_put(t->bt_mp, h, 0);
	243	}
	244
	245	/* Restore the stack. */
	246	while (level--) {
	247	/* Push the next level down onto the stack. */
1f2f436a	248	bi = GETBINTERNAL(h, idx);
9385eb3d A	249	pgno = bi->pgno;
	250
	251	/* Lose the currently pinned page. */
	252	mpool_put(t->bt_mp, h, 0);
	253
	254	/* Get the next level down. */
	255	if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL)
	256	return (1);
	257
1f2f436a A	258	idx = NEXTINDEX(h) - 1;
1f2f436a A	259	BT_PUSH(t, pgno, idx);
9385eb3d A	260	}
	261	mpool_put(t->bt_mp, h, 0);
	262	if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL)
	263	return (1);
	264	}
1f2f436a	265
9385eb3d A	266
	267	ret: mpool_put(t->bt_mp, h, 0);
	268	return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL);
	269	}
	270
	271	/*
	272	* __bt_bdelete --
	273	* Delete all key/data pairs matching the specified key.
	274	*
	275	* Parameters:
	276	* t: tree
e9ce8d39 A	277	* key: key to delete
	278	*
	279	* Returns:
	280	* RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
	281	*/
	282	static int
1f2f436a	283	__bt_bdelete(BTREE t, const DBT key)
e9ce8d39	284	{
9385eb3d	285	EPG *e;
e9ce8d39	286	PAGE *h;
9385eb3d A	287	int deleted, exact, redo;
	288
	289	deleted = 0;
e9ce8d39 A	290
e9ce8d39 A	291	/* Find any matching record; __bt_search pins the page. */
9385eb3d A	292	loop: if ((e = __bt_search(t, key, &exact)) == NULL)
9385eb3d A	293	return (deleted ? RET_SUCCESS : RET_ERROR);
e9ce8d39 A	294	if (!exact) {
e9ce8d39 A	295	mpool_put(t->bt_mp, e->page, 0);
9385eb3d	296	return (deleted ? RET_SUCCESS : RET_SPECIAL);
e9ce8d39 A	297	}
	298
	299	/*
9385eb3d A	300	* Delete forward, then delete backward, from the found key. If
	301	* there are duplicates and we reach either side of the page, do
	302	* the key search again, so that we get them all.
e9ce8d39	303	*/
9385eb3d A	304	redo = 0;
	305	h = e->page;
	306	do {
	307	if (__bt_dleaf(t, key, h, e->index)) {
	308	mpool_put(t->bt_mp, h, 0);
	309	return (RET_ERROR);
	310	}
	311	if (F_ISSET(t, B_NODUPS)) {
	312	if (NEXTINDEX(h) == 0) {
	313	if (__bt_pdelete(t, h))
e9ce8d39	314	return (RET_ERROR);
9385eb3d A	315	} else
	316	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
	317	return (RET_SUCCESS);
e9ce8d39	318	}
9385eb3d A	319	deleted = 1;
	320	} while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
	321
	322	/* Check for right-hand edge of the page. */
	323	if (e->index == NEXTINDEX(h))
	324	redo = 1;
e9ce8d39	325
9385eb3d A	326	/* Delete from the key to the beginning of the page. */
9385eb3d A	327	while (e->index-- > 0) {
e9ce8d39 A	328	if (__bt_cmp(t, key, e) != 0)
e9ce8d39 A	329	break;
9385eb3d A	330	if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) {
	331	mpool_put(t->bt_mp, h, 0);
	332	return (RET_ERROR);
	333	}
	334	if (e->index == 0)
	335	redo = 1;
e9ce8d39 A	336	}
e9ce8d39 A	337
9385eb3d A	338	/* Check for an empty page. */
	339	if (NEXTINDEX(h) == 0) {
	340	if (__bt_pdelete(t, h))
	341	return (RET_ERROR);
	342	goto loop;
	343	}
	344
	345	/* Put the page. */
	346	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
	347
	348	if (redo)
	349	goto loop;
	350	return (RET_SUCCESS);
	351	}
	352
	353	/*
	354	* __bt_pdelete --
	355	* Delete a single page from the tree.
	356	*
	357	* Parameters:
	358	* t: tree
	359	* h: leaf page
	360	*
	361	* Returns:
	362	* RET_SUCCESS, RET_ERROR.
	363	*
	364	* Side-effects:
	365	* mpool_put's the page
	366	*/
	367	static int
1f2f436a	368	__bt_pdelete(BTREE t, PAGE h)
9385eb3d A	369	{
	370	BINTERNAL *bi;
	371	PAGE *pg;
	372	EPGNO *parent;
1f2f436a	373	indx_t cnt, idx, *ip, offset;
9385eb3d A	374	u_int32_t nksize;
9385eb3d A	375	char *from;
e9ce8d39 A	376
e9ce8d39 A	377	/*
9385eb3d A	378	* Walk the parent page stack -- a LIFO stack of the pages that were
	379	* traversed when we searched for the page where the delete occurred.
	380	* Each stack entry is a page number and a page index offset. The
	381	* offset is for the page traversed on the search. We've just deleted
	382	* a page, so we have to delete the key from the parent page.
	383	*
	384	* If the delete from the parent page makes it empty, this process may
	385	* continue all the way up the tree. We stop if we reach the root page
	386	* (which is never deleted, it's just not worth the effort) or if the
	387	* delete does not empty the page.
e9ce8d39	388	*/
9385eb3d A	389	while ((parent = BT_POP(t)) != NULL) {
	390	/* Get the parent page. */
	391	if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL)
	392	return (RET_ERROR);
1f2f436a A	393
	394	idx = parent->index;
	395	bi = GETBINTERNAL(pg, idx);
9385eb3d A	396
	397	/* Free any overflow pages. */
	398	if (bi->flags & P_BIGKEY &&
	399	__ovfl_delete(t, bi->bytes) == RET_ERROR) {
	400	mpool_put(t->bt_mp, pg, 0);
	401	return (RET_ERROR);
	402	}
	403
	404	/*
	405	* Free the parent if it has only the one key and it's not the
	406	* root page. If it's the rootpage, turn it back into an empty
	407	* leaf page.
	408	*/
1f2f436a	409	if (NEXTINDEX(pg) == 1) {
9385eb3d A	410	if (pg->pgno == P_ROOT) {
	411	pg->lower = BTDATAOFF;
	412	pg->upper = t->bt_psize;
	413	pg->flags = P_BLEAF;
e9ce8d39	414	} else {
9385eb3d	415	if (__bt_relink(t, pg) \|\| __bt_free(t, pg))
e9ce8d39	416	return (RET_ERROR);
9385eb3d	417	continue;
e9ce8d39	418	}
1f2f436a	419	} else {
9385eb3d A	420	/* Pack remaining key items at the end of the page. */
	421	nksize = NBINTERNAL(bi->ksize);
	422	from = (char *)pg + pg->upper;
	423	memmove(from + nksize, from, (char *)bi - from);
	424	pg->upper += nksize;
	425
	426	/* Adjust indices' offsets, shift the indices down. */
1f2f436a A	427	offset = pg->linp[idx];
1f2f436a A	428	for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip)
9385eb3d A	429	if (ip[0] < offset)
9385eb3d A	430	ip[0] += nksize;
1f2f436a	431	for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip)
9385eb3d A	432	ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1];
9385eb3d A	433	pg->lower -= sizeof(indx_t);
e9ce8d39 A	434	}
e9ce8d39 A	435
9385eb3d A	436	mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
9385eb3d A	437	break;
e9ce8d39 A	438	}
e9ce8d39 A	439
9385eb3d A	440	/* Free the leaf page, as long as it wasn't the root. */
	441	if (h->pgno == P_ROOT) {
	442	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
	443	return (RET_SUCCESS);
	444	}
	445	return (__bt_relink(t, h) \|\| __bt_free(t, h));
e9ce8d39 A	446	}
	447
	448	/*
9385eb3d A	449	* __bt_dleaf --
9385eb3d A	450	* Delete a single record from a leaf page.
e9ce8d39 A	451	*
	452	* Parameters:
	453	* t: tree
9385eb3d A	454	* key: referenced key
9385eb3d A	455	* h: page
1f2f436a	456	* idx: index on page to delete
e9ce8d39 A	457	*
	458	* Returns:
	459	* RET_SUCCESS, RET_ERROR.
	460	*/
	461	int
1f2f436a	462	__bt_dleaf(BTREE t, const DBT key, PAGE *h, u_int idx)
e9ce8d39	463	{
9385eb3d A	464	BLEAF *bl;
	465	indx_t cnt, *ip, offset;
	466	u_int32_t nbytes;
e9ce8d39	467	void *to;
9385eb3d	468	char *from;
e9ce8d39	469
9385eb3d A	470	/* If this record is referenced by the cursor, delete the cursor. */
	471	if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
	472	!F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
1f2f436a A	473	t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx &&
1f2f436a A	474	__bt_curdel(t, key, h, idx))
9385eb3d A	475	return (RET_ERROR);
	476
	477	/* If the entry uses overflow pages, make them available for reuse. */
1f2f436a	478	to = bl = GETBLEAF(h, idx);
e9ce8d39 A	479	if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
	480	return (RET_ERROR);
	481	if (bl->flags & P_BIGDATA &&
	482	__ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
	483	return (RET_ERROR);
e9ce8d39	484
9385eb3d A	485	/* Pack the remaining key/data items at the end of the page. */
9385eb3d A	486	nbytes = NBLEAF(bl);
e9ce8d39 A	487	from = (char *)h + h->upper;
	488	memmove(from + nbytes, from, (char *)to - from);
	489	h->upper += nbytes;
	490
9385eb3d	491	/* Adjust the indices' offsets, shift the indices down. */
1f2f436a A	492	offset = h->linp[idx];
1f2f436a A	493	for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip)
e9ce8d39 A	494	if (ip[0] < offset)
e9ce8d39 A	495	ip[0] += nbytes;
1f2f436a	496	for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip)
e9ce8d39 A	497	ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
e9ce8d39 A	498	h->lower -= sizeof(indx_t);
9385eb3d A	499
	500	/* If the cursor is on this page, adjust it as necessary. */
	501	if (F_ISSET(&t->bt_cursor, CURS_INIT) &&
	502	!F_ISSET(&t->bt_cursor, CURS_ACQUIRE) &&
1f2f436a	503	t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx)
9385eb3d A	504	--t->bt_cursor.pg.index;
9385eb3d A	505
e9ce8d39 A	506	return (RET_SUCCESS);
e9ce8d39 A	507	}
9385eb3d A	508
	509	/*
	510	* __bt_curdel --
	511	* Delete the cursor.
	512	*
	513	* Parameters:
	514	* t: tree
	515	* key: referenced key (or NULL)
	516	* h: page
1f2f436a	517	* idx: index on page to delete
9385eb3d A	518	*
	519	* Returns:
	520	* RET_SUCCESS, RET_ERROR.
	521	*/
	522	static int
1f2f436a	523	__bt_curdel(BTREE t, const DBT key, PAGE *h, u_int idx)
9385eb3d A	524	{
	525	CURSOR *c;
	526	EPG e;
	527	PAGE *pg;
	528	int curcopy, status;
	529
	530	/*
	531	* If there are duplicates, move forward or backward to one.
	532	* Otherwise, copy the key into the cursor area.
	533	*/
	534	c = &t->bt_cursor;
	535	F_CLR(c, CURS_AFTER \| CURS_BEFORE \| CURS_ACQUIRE);
	536
	537	curcopy = 0;
	538	if (!F_ISSET(t, B_NODUPS)) {
	539	/*
	540	* We're going to have to do comparisons. If we weren't
	541	* provided a copy of the key, i.e. the user is deleting
	542	* the current cursor position, get one.
	543	*/
	544	if (key == NULL) {
	545	e.page = h;
1f2f436a	546	e.index = idx;
9385eb3d A	547	if ((status = __bt_ret(t, &e,
	548	&c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS)
	549	return (status);
	550	curcopy = 1;
	551	key = &c->key;
	552	}
	553	/* Check previous key, if not at the beginning of the page. */
1f2f436a	554	if (idx > 0) {
9385eb3d	555	e.page = h;
1f2f436a	556	e.index = idx - 1;
9385eb3d A	557	if (__bt_cmp(t, key, &e) == 0) {
	558	F_SET(c, CURS_BEFORE);
	559	goto dup2;
	560	}
	561	}
	562	/* Check next key, if not at the end of the page. */
1f2f436a	563	if (idx < NEXTINDEX(h) - 1) {
9385eb3d	564	e.page = h;
1f2f436a	565	e.index = idx + 1;
9385eb3d A	566	if (__bt_cmp(t, key, &e) == 0) {
	567	F_SET(c, CURS_AFTER);
	568	goto dup2;
	569	}
	570	}
	571	/* Check previous key if at the beginning of the page. */
1f2f436a	572	if (idx == 0 && h->prevpg != P_INVALID) {
9385eb3d A	573	if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
	574	return (RET_ERROR);
	575	e.page = pg;
	576	e.index = NEXTINDEX(pg) - 1;
	577	if (__bt_cmp(t, key, &e) == 0) {
	578	F_SET(c, CURS_BEFORE);
	579	goto dup1;
	580	}
	581	mpool_put(t->bt_mp, pg, 0);
	582	}
	583	/* Check next key if at the end of the page. */
1f2f436a	584	if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) {
9385eb3d A	585	if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
	586	return (RET_ERROR);
	587	e.page = pg;
	588	e.index = 0;
	589	if (__bt_cmp(t, key, &e) == 0) {
	590	F_SET(c, CURS_AFTER);
	591	dup1: mpool_put(t->bt_mp, pg, 0);
	592	dup2: c->pg.pgno = e.page->pgno;
	593	c->pg.index = e.index;
	594	return (RET_SUCCESS);
	595	}
	596	mpool_put(t->bt_mp, pg, 0);
	597	}
	598	}
	599	e.page = h;
1f2f436a	600	e.index = idx;
9385eb3d A	601	if (curcopy \|\| (status =
	602	__bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) {
	603	F_SET(c, CURS_ACQUIRE);
	604	return (RET_SUCCESS);
	605	}
	606	return (status);
	607	}
	608
	609	/*
	610	* __bt_relink --
	611	* Link around a deleted page.
	612	*
	613	* Parameters:
	614	* t: tree
	615	* h: page to be deleted
	616	*/
	617	static int
1f2f436a	618	__bt_relink(BTREE t, PAGE h)
9385eb3d A	619	{
	620	PAGE *pg;
	621
	622	if (h->nextpg != P_INVALID) {
	623	if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL)
	624	return (RET_ERROR);
	625	pg->prevpg = h->prevpg;
	626	mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
	627	}
	628	if (h->prevpg != P_INVALID) {
	629	if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL)
	630	return (RET_ERROR);
	631	pg->nextpg = h->nextpg;
	632	mpool_put(t->bt_mp, pg, MPOOL_DIRTY);
	633	}
	634	return (0);
	635	}