1#pragma ident	"%Z%%M%	%I%	%E% SMI"
2
3/*-
4 * Copyright (c) 1990, 1993, 1994
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Mike Olson.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. All advertising materials mentioning features or use of this software
19 *    must display the following acknowledgement:
20 *	This product includes software developed by the University of
21 *	California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 *    may be used to endorse or promote products derived from this software
24 *    without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 */
38
39#if defined(LIBC_SCCS) && !defined(lint)
40static char sccsid[] = "@(#)rec_delete.c	8.7 (Berkeley) 7/14/94";
41#endif /* LIBC_SCCS and not lint */
42
43#include <sys/types.h>
44
45#include <errno.h>
46#include <stdio.h>
47#include <string.h>
48
49#include "db-int.h"
50#include "recno.h"
51
52static int rec_rdelete __P((BTREE *, recno_t));
53
54/*
55 * __REC_DELETE -- Delete the item(s) referenced by a key.
56 *
57 * Parameters:
58 *	dbp:	pointer to access method
59 *	key:	key to delete
60 *	flags:	R_CURSOR if deleting what the cursor references
61 *
62 * Returns:
63 *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
64 */
65int
66__rec_delete(dbp, key, flags)
67	const DB *dbp;
68	const DBT *key;
69	u_int flags;
70{
71	BTREE *t;
72	recno_t nrec;
73	int status;
74
75	t = dbp->internal;
76
77	/* Toss any page pinned across calls. */
78	if (t->bt_pinned != NULL) {
79		mpool_put(t->bt_mp, t->bt_pinned, 0);
80		t->bt_pinned = NULL;
81	}
82
83	switch(flags) {
84	case 0:
85		if ((nrec = *(recno_t *)key->data) == 0)
86			goto einval;
87		if (nrec > t->bt_nrecs)
88			return (RET_SPECIAL);
89		--nrec;
90		status = rec_rdelete(t, nrec);
91		break;
92	case R_CURSOR:
93		if (!F_ISSET(&t->bt_cursor, CURS_INIT))
94			goto einval;
95		if (t->bt_nrecs == 0)
96			return (RET_SPECIAL);
97		status = rec_rdelete(t, t->bt_cursor.rcursor - 1);
98		if (status == RET_SUCCESS)
99			--t->bt_cursor.rcursor;
100		break;
101	default:
102einval:		errno = EINVAL;
103		return (RET_ERROR);
104	}
105
106	if (status == RET_SUCCESS)
107		F_SET(t, B_MODIFIED | R_MODIFIED);
108	return (status);
109}
110
111/*
112 * REC_RDELETE -- Delete the data matching the specified key.
113 *
114 * Parameters:
115 *	tree:	tree
116 *	nrec:	record to delete
117 *
118 * Returns:
119 *	RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
120 */
121static int
122rec_rdelete(t, nrec)
123	BTREE *t;
124	recno_t nrec;
125{
126	EPG *e;
127	PAGE *h;
128	int status;
129
130	/* Find the record; __rec_search pins the page. */
131	if ((e = __rec_search(t, nrec, SDELETE)) == NULL)
132		return (RET_ERROR);
133
134	/* Delete the record. */
135	h = e->page;
136	status = __rec_dleaf(t, h, e->index);
137	if (status != RET_SUCCESS) {
138		mpool_put(t->bt_mp, h, 0);
139		return (status);
140	}
141	mpool_put(t->bt_mp, h, MPOOL_DIRTY);
142	return (RET_SUCCESS);
143}
144
145/*
146 * __REC_DLEAF -- Delete a single record from a recno leaf page.
147 *
148 * Parameters:
149 *	t:	tree
150 *	idx:	index on current page to delete
151 *
152 * Returns:
153 *	RET_SUCCESS, RET_ERROR.
154 */
155int
156__rec_dleaf(t, h, idx)
157	BTREE *t;
158	PAGE *h;
159	u_int32_t idx;
160{
161	RLEAF *rl;
162	indx_t *ip, cnt, offset;
163	u_int32_t nbytes;
164	char *from;
165	void *to;
166
167	/*
168	 * Delete a record from a recno leaf page.  Internal records are never
169	 * deleted from internal pages, regardless of the records that caused
170	 * them to be added being deleted.  Pages made empty by deletion are
171	 * not reclaimed.  They are, however, made available for reuse.
172	 *
173	 * Pack the remaining entries at the end of the page, shift the indices
174	 * down, overwriting the deleted record and its index.  If the record
175	 * uses overflow pages, make them available for reuse.
176	 */
177	to = rl = GETRLEAF(h, idx);
178	if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR)
179		return (RET_ERROR);
180	nbytes = NRLEAF(rl);
181
182	/*
183	 * Compress the key/data pairs.  Compress and adjust the [BR]LEAF
184	 * offsets.  Reset the headers.
185	 */
186	from = (char *)h + h->upper;
187	memmove(from + nbytes, from, (char *)to - from);
188	h->upper += nbytes;
189
190	offset = h->linp[idx];
191	for (cnt = &h->linp[idx] - (ip = &h->linp[0]); cnt--; ++ip)
192		if (ip[0] < offset)
193			ip[0] += nbytes;
194	for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip)
195		ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1];
196	h->lower -= sizeof(indx_t);
197	--t->bt_nrecs;
198	return (RET_SUCCESS);
199}
200