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