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

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