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)
40 static 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
52 static 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 */
65 int
__rec_delete(dbp,key,flags)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:
102 einval: 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 */
121 static int
rec_rdelete(t,nrec)122 rec_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 */
155 int
__rec_dleaf(t,h,idx)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