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

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 * Copyright (c) 1990, 1993
 *	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.
 */


#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 *));

/*
 * __BT_DELETE -- Delete the item(s) referenced by a key.
 *
 * Parameters:
 *	dbp:	pointer to access method
 *	key:	key to delete
 *	flags:	R_CURSOR if deleting what the cursor references
 *
 * Returns:
 *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
 */
int
__bt_delete(dbp, key, flags)
	const DB *dbp;
	const DBT *key;
	u_int flags;
{
	BTREE *t;
	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;
	}

	if (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 the record.  For
		 * the delete cursor bit to have been set requires that the
		 * scan be initialized, so no reason to check.
		 */
		if (!ISSET(t, B_SEQINIT))
                        goto einval;
		status = ISSET(t, B_DELCRSR) ?
		    RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor);
		break;
	default:
einval:		errno = EINVAL;
		return (RET_ERROR);
	}
	if (status == RET_SUCCESS)
		SET(t, B_MODIFIED);
	return (status);
}

/*
 * BT_BDELETE -- Delete all key/data pairs matching the specified key.
 *
 * Parameters:
 *	tree:	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, save;
	PAGE *h;
	pgno_t cpgno, pg;
	indx_t cindex;
	int deleted, dirty1, dirty2, exact;

	/* Find any matching record; __bt_search pins the page. */
	if ((e = __bt_search(t, key, &exact)) == NULL)
		return (RET_ERROR);
	if (!exact) {
		mpool_put(t->bt_mp, e->page, 0);
		return (RET_SPECIAL);
	}

	/*
	 * Delete forward, then delete backward, from the found key.  The
	 * ordering is so that the deletions don't mess up the page refs.
	 * The first loop deletes the key from the original page, the second
	 * unpins the original page.  In the first loop, dirty1 is set if
	 * the original page is modified, and dirty2 is set if any subsequent
	 * pages are modified.  In the second loop, dirty1 starts off set if
	 * the original page has been modified, and is set if any subsequent
	 * pages are modified.
	 *
	 * If find the key referenced by the cursor, don't delete it, just
	 * flag it for future deletion.  The cursor page number is P_INVALID
	 * unless the sequential scan is initialized, so no reason to check.
	 * A special case is when the already deleted cursor record was the
	 * only record found.  If so, then the delete opertion fails as no
	 * records were deleted.
	 *
	 * Cycle in place in the current page until the current record doesn't
	 * match the key or the page is empty.  If the latter, walk forward,
	 * skipping empty pages and repeating until a record doesn't match
	 * the key or the end of the tree is reached.
	 */
	cpgno = t->bt_bcursor.pgno;
	cindex = t->bt_bcursor.index;
	save = *e;
	dirty1 = 0;
	for (h = e->page, deleted = 0;;) {
		dirty2 = 0;
		do {
			if (h->pgno == cpgno && e->index == cindex) {
				if (!ISSET(t, B_DELCRSR)) {
					SET(t, B_DELCRSR);
					deleted = 1;
				}
				++e->index;
			} else {
				if (__bt_dleaf(t, h, e->index)) {
					if (h->pgno != save.page->pgno)
						mpool_put(t->bt_mp, h, dirty2);
					mpool_put(t->bt_mp, save.page, dirty1);
					return (RET_ERROR);
				}
				if (h->pgno == save.page->pgno)
					dirty1 = MPOOL_DIRTY;
				else
					dirty2 = MPOOL_DIRTY;
				deleted = 1;
			}
		} while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);

		/*
		 * Quit if didn't find a match, no next page, or first key on
		 * the next page doesn't match.  Don't unpin the original page
		 * unless an error occurs.
		 */
		if (e->index < NEXTINDEX(h))
			break;
		for (;;) {
			if ((pg = h->nextpg) == P_INVALID)
				goto done1;
			if (h->pgno != save.page->pgno)
				mpool_put(t->bt_mp, h, dirty2);
			if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) {
				mpool_put(t->bt_mp, save.page, dirty1);
				return (RET_ERROR);
			}
			if (NEXTINDEX(h) != 0) {
				e->page = h;
				e->index = 0;
				break;
			}
		}

		if (__bt_cmp(t, key, e) != 0)
			break;
	}

	/*
	 * Reach here with the original page and the last page referenced
	 * pinned (they may be the same).  Release it if not the original.
	 */
done1:	if (h->pgno != save.page->pgno)
		mpool_put(t->bt_mp, h, dirty2);

	/*
	 * Walk backwards from the record previous to the record returned by
	 * __bt_search, skipping empty pages, until a record doesn't match
	 * the key or reach the beginning of the tree.
	 */
	*e = save;
	for (;;) {
		if (e->index)
			--e->index;
		for (h = e->page; e->index; --e->index) {
			if (__bt_cmp(t, key, e) != 0)
				goto done2;
			if (h->pgno == cpgno && e->index == cindex) {
				if (!ISSET(t, B_DELCRSR)) {
					SET(t, B_DELCRSR);
					deleted = 1;
				}
			} else {
				if (__bt_dleaf(t, h, e->index) == RET_ERROR) {
					mpool_put(t->bt_mp, h, dirty1);
					return (RET_ERROR);
				}
				if (h->pgno == save.page->pgno)
					dirty1 = MPOOL_DIRTY;
				deleted = 1;
			}
		}

		if ((pg = h->prevpg) == P_INVALID)
			goto done2;
		mpool_put(t->bt_mp, h, dirty1);
		dirty1 = 0;
		if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL)
			return (RET_ERROR);
		e->index = NEXTINDEX(e->page);
	}

	/*
	 * Reach here with the last page that was looked at pinned.  Release
	 * it.
	 */
done2:	mpool_put(t->bt_mp, h, dirty1);
	return (deleted ? RET_SUCCESS : RET_SPECIAL);
}

/*
 * __BT_DLEAF -- Delete a single record from a leaf page.
 *
 * Parameters:
 *	t:	tree
 *	index:	index on current page to delete
 *
 * Returns:
 *	RET_SUCCESS, RET_ERROR.
 */
int
__bt_dleaf(t, h, index)
	BTREE *t;
	PAGE *h;
	indx_t index;
{
	register BLEAF *bl;
	register indx_t cnt, *ip, offset;
	register size_t nbytes;
	char *from;
	void *to;

	/*
	 * Delete a record from a btree leaf page.  Internal records are never
	 * deleted from internal pages, regardless of the records that caused
	 * them to be added being deleted.  Pages made empty by deletion are
	 * not reclaimed.  They are, however, made available for reuse.
	 *
	 * Pack the remaining entries at the end of the page, shift the indices
	 * down, overwriting the deleted record and its index.  If the record
	 * 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);
	nbytes = NBLEAF(bl);

	/*
	 * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
	 * offsets.  Reset the headers.
	 */
	from = (char *)h + h->upper;
	memmove(from + nbytes, from, (char *)to - from);
	h->upper += nbytes;

	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);
	return (RET_SUCCESS);
}
Commit	Line	Data
e9ce8d39 A	1	/*
	2	* Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
734aad71	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
e9ce8d39	7	*
734aad71 A	8	* This file contains Original Code and/or Modifications of Original Code
	9	* as defined in and that are subject to the Apple Public Source License
	10	* Version 2.0 (the 'License'). You may not use this file except in
	11	* compliance with the License. Please obtain a copy of the License at
	12	* http://www.opensource.apple.com/apsl/ and read it before using this
	13	* file.
	14	*
	15	* The Original Code and all software distributed under the License are
	16	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
e9ce8d39 A	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
e9ce8d39 A	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
734aad71 A	19	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	20	* Please see the License for the specific language governing rights and
	21	* limitations under the License.
e9ce8d39 A	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
	25	/*
	26	* Copyright (c) 1990, 1993
	27	* The Regents of the University of California. All rights reserved.
	28	*
	29	* This code is derived from software contributed to Berkeley by
	30	* Mike Olson.
	31	*
	32	* Redistribution and use in source and binary forms, with or without
	33	* modification, are permitted provided that the following conditions
	34	* are met:
	35	* 1. Redistributions of source code must retain the above copyright
	36	* notice, this list of conditions and the following disclaimer.
	37	* 2. Redistributions in binary form must reproduce the above copyright
	38	* notice, this list of conditions and the following disclaimer in the
	39	* documentation and/or other materials provided with the distribution.
	40	* 3. All advertising materials mentioning features or use of this software
	41	* must display the following acknowledgement:
	42	* This product includes software developed by the University of
	43	* California, Berkeley and its contributors.
	44	* 4. Neither the name of the University nor the names of its contributors
	45	* may be used to endorse or promote products derived from this software
	46	* without specific prior written permission.
	47	*
	48	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	49	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	50	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	51	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	52	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	53	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	54	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	55	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	56	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	57	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	58	* SUCH DAMAGE.
	59	*/
	60
	61
	62	#include <sys/types.h>
	63
	64	#include <errno.h>
	65	#include <stdio.h>
	66	#include <string.h>
	67
	68	#include <db.h>
	69	#include "btree.h"
	70
	71	static int bt_bdelete __P((BTREE , const DBT ));
	72
	73	/*
	74	* __BT_DELETE -- Delete the item(s) referenced by a key.
	75	*
	76	* Parameters:
	77	* dbp: pointer to access method
	78	* key: key to delete
	79	* flags: R_CURSOR if deleting what the cursor references
	80	*
	81	* Returns:
	82	* RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
	83	*/
	84	int
	85	__bt_delete(dbp, key, flags)
86	const DB *dbp;
87	const DBT *key;
88	u_int flags;
89	{
90	BTREE *t;
91	int status;
92
93	t = dbp->internal;
94
95	/* Toss any page pinned across calls. */
96	if (t->bt_pinned != NULL) {
97	mpool_put(t->bt_mp, t->bt_pinned, 0);
98	t->bt_pinned = NULL;
99	}
100
101	if (ISSET(t, B_RDONLY)) {
102	errno = EPERM;
103	return (RET_ERROR);
104	}
105
106	switch(flags) {
107	case 0:
108	status = bt_bdelete(t, key);
109	break;
110	case R_CURSOR:
111	/*
112	* If flags is R_CURSOR, delete the cursor; must already have
113	* started a scan and not have already deleted the record. For
114	* the delete cursor bit to have been set requires that the
115	* scan be initialized, so no reason to check.
116	*/
117	if (!ISSET(t, B_SEQINIT))
118	goto einval;
119	status = ISSET(t, B_DELCRSR) ?
120	RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor);
121	break;
122	default:
123	einval: errno = EINVAL;
124	return (RET_ERROR);
125	}
126	if (status == RET_SUCCESS)
127	SET(t, B_MODIFIED);
128	return (status);
129	}
130
131	/*
132	* BT_BDELETE -- Delete all key/data pairs matching the specified key.
133	*
134	* Parameters:
135	* tree: tree
136	* key: key to delete
137	*
138	* Returns:
139	* RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
140	*/
141	static int
142	bt_bdelete(t, key)
143	BTREE *t;
144	const DBT *key;
145	{
146	EPG *e, save;
147	PAGE *h;
148	pgno_t cpgno, pg;
149	indx_t cindex;
150	int deleted, dirty1, dirty2, exact;
151
152	/* Find any matching record; __bt_search pins the page. */
153	if ((e = __bt_search(t, key, &exact)) == NULL)
154	return (RET_ERROR);
155	if (!exact) {
156	mpool_put(t->bt_mp, e->page, 0);
157	return (RET_SPECIAL);
158	}
159
160	/*
161	* Delete forward, then delete backward, from the found key. The
162	* ordering is so that the deletions don't mess up the page refs.
163	* The first loop deletes the key from the original page, the second
164	* unpins the original page. In the first loop, dirty1 is set if
165	* the original page is modified, and dirty2 is set if any subsequent
166	* pages are modified. In the second loop, dirty1 starts off set if
167	* the original page has been modified, and is set if any subsequent
168	* pages are modified.
169	*
170	* If find the key referenced by the cursor, don't delete it, just
171	* flag it for future deletion. The cursor page number is P_INVALID
172	* unless the sequential scan is initialized, so no reason to check.
173	* A special case is when the already deleted cursor record was the
174	* only record found. If so, then the delete opertion fails as no
175	* records were deleted.
176	*
177	* Cycle in place in the current page until the current record doesn't
178	* match the key or the page is empty. If the latter, walk forward,
179	* skipping empty pages and repeating until a record doesn't match
180	* the key or the end of the tree is reached.
181	*/
182	cpgno = t->bt_bcursor.pgno;
183	cindex = t->bt_bcursor.index;
184	save = *e;
185	dirty1 = 0;
186	for (h = e->page, deleted = 0;;) {
187	dirty2 = 0;
188	do {
189	if (h->pgno == cpgno && e->index == cindex) {
190	if (!ISSET(t, B_DELCRSR)) {
191	SET(t, B_DELCRSR);
192	deleted = 1;
193	}
194	++e->index;
195	} else {
196	if (__bt_dleaf(t, h, e->index)) {
197	if (h->pgno != save.page->pgno)
198	mpool_put(t->bt_mp, h, dirty2);
199	mpool_put(t->bt_mp, save.page, dirty1);
200	return (RET_ERROR);
201	}
202	if (h->pgno == save.page->pgno)
203	dirty1 = MPOOL_DIRTY;
204	else
205	dirty2 = MPOOL_DIRTY;
206	deleted = 1;
207	}
208	} while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0);
209
210	/*
211	* Quit if didn't find a match, no next page, or first key on
212	* the next page doesn't match. Don't unpin the original page
213	* unless an error occurs.
214	*/
215	if (e->index < NEXTINDEX(h))
216	break;
217	for (;;) {
218	if ((pg = h->nextpg) == P_INVALID)
219	goto done1;
220	if (h->pgno != save.page->pgno)
221	mpool_put(t->bt_mp, h, dirty2);
222	if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) {
223	mpool_put(t->bt_mp, save.page, dirty1);
224	return (RET_ERROR);
225	}
226	if (NEXTINDEX(h) != 0) {
227	e->page = h;
228	e->index = 0;
229	break;
230	}
231	}
232
233	if (__bt_cmp(t, key, e) != 0)
234	break;
235	}
236
237	/*
238	* Reach here with the original page and the last page referenced
239	* pinned (they may be the same). Release it if not the original.
240	*/
241	done1: if (h->pgno != save.page->pgno)
242	mpool_put(t->bt_mp, h, dirty2);
243
244	/*
245	* Walk backwards from the record previous to the record returned by
246	* __bt_search, skipping empty pages, until a record doesn't match
247	* the key or reach the beginning of the tree.
248	*/
249	*e = save;
250	for (;;) {
251	if (e->index)
252	--e->index;
253	for (h = e->page; e->index; --e->index) {
254	if (__bt_cmp(t, key, e) != 0)
255	goto done2;
256	if (h->pgno == cpgno && e->index == cindex) {
257	if (!ISSET(t, B_DELCRSR)) {
258	SET(t, B_DELCRSR);
259	deleted = 1;
260	}
261	} else {
262	if (__bt_dleaf(t, h, e->index) == RET_ERROR) {
263	mpool_put(t->bt_mp, h, dirty1);
264	return (RET_ERROR);
265	}
266	if (h->pgno == save.page->pgno)
267	dirty1 = MPOOL_DIRTY;
268	deleted = 1;
269	}
270	}
271
272	if ((pg = h->prevpg) == P_INVALID)
273	goto done2;
274	mpool_put(t->bt_mp, h, dirty1);
275	dirty1 = 0;
276	if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL)
277	return (RET_ERROR);
278	e->index = NEXTINDEX(e->page);
279	}
280
281	/*
282	* Reach here with the last page that was looked at pinned. Release
283	* it.
284	*/
285	done2: mpool_put(t->bt_mp, h, dirty1);
286	return (deleted ? RET_SUCCESS : RET_SPECIAL);
287	}
288
289	/*
290	* __BT_DLEAF -- Delete a single record from a leaf page.
291	*
292	* Parameters:
293	* t: tree
294	* index: index on current page to delete
295	*
296	* Returns:
297	* RET_SUCCESS, RET_ERROR.
298	*/
299	int
300	__bt_dleaf(t, h, index)
301	BTREE *t;
302	PAGE *h;
303	indx_t index;
304	{
305	register BLEAF *bl;
306	register indx_t cnt, *ip, offset;
307	register size_t nbytes;
308	char *from;
309	void *to;
310
311	/*
312	* Delete a record from a btree leaf page. Internal records are never
313	* deleted from internal pages, regardless of the records that caused
314	* them to be added being deleted. Pages made empty by deletion are
315	* not reclaimed. They are, however, made available for reuse.
316	*
317	* Pack the remaining entries at the end of the page, shift the indices
318	* down, overwriting the deleted record and its index. If the record
319	* uses overflow pages, make them available for reuse.
320	*/
321	to = bl = GETBLEAF(h, index);
322	if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR)
323	return (RET_ERROR);
324	if (bl->flags & P_BIGDATA &&
325	__ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR)
326	return (RET_ERROR);
327	nbytes = NBLEAF(bl);
328
329	/*
330	* Compress the key/data pairs. Compress and adjust the [BR]LEAF
331	* offsets. Reset the headers.
332	*/
333	from = (char *)h + h->upper;
334	memmove(from + nbytes, from, (char *)to - from);
335	h->upper += nbytes;
336
337	offset = h->linp[index];
338	for (cnt = index, ip = &h->linp[0]; cnt--; ++ip)
339	if (ip[0] < offset)
340	ip[0] += nbytes;
341	for (cnt = NEXTINDEX(h) - index; --cnt; ++ip)
342	ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
343	h->lower -= sizeof(indx_t);
344	return (RET_SUCCESS);
345	}