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[] = "@(#)bt_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 "btree.h" 49 50 static int bt_bdelete __P((BTREE *, const DBT *)); 51 52 /* 53 * __BT_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 __bt_delete(dbp, key, flags) 65 const DB *dbp; 66 const DBT *key; 67 u_int flags; 68 { 69 BTREE *t; 70 int status; 71 72 t = dbp->internal; 73 if (ISSET(t, B_RDONLY)) { 74 errno = EPERM; 75 return (RET_ERROR); 76 } 77 switch(flags) { 78 case 0: 79 status = bt_bdelete(t, key); 80 break; 81 case R_CURSOR: 82 /* 83 * If flags is R_CURSOR, delete the cursor; must already have 84 * started a scan and not have already deleted the record. For 85 * the delete cursor bit to have been set requires that the 86 * scan be initialized, so no reason to check. 87 */ 88 if (!ISSET(t, B_SEQINIT)) 89 goto einval; 90 status = ISSET(t, B_DELCRSR) ? 91 RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor); 92 break; 93 default: 94 einval: errno = EINVAL; 95 return (RET_ERROR); 96 } 97 if (status == RET_SUCCESS) 98 SET(t, B_MODIFIED); 99 return (status); 100 } 101 102 /* 103 * BT_BDELETE -- Delete all key/data pairs matching the specified key. 104 * 105 * Parameters: 106 * tree: tree 107 * key: key to delete 108 * 109 * Returns: 110 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 111 */ 112 static int 113 bt_bdelete(t, key) 114 BTREE *t; 115 const DBT *key; 116 { 117 EPG *e, save; 118 PAGE *h; 119 pgno_t cpgno, pg; 120 indx_t cindex; 121 int deleted, dirty1, dirty2, exact; 122 123 /* Find any matching record; __bt_search pins the page. */ 124 if ((e = __bt_search(t, key, &exact)) == NULL) 125 return (RET_ERROR); 126 if (!exact) { 127 mpool_put(t->bt_mp, e->page, 0); 128 return (RET_SPECIAL); 129 } 130 131 /* 132 * Delete forward, then delete backward, from the found key. The 133 * ordering is so that the deletions don't mess up the page refs. 134 * The first loop deletes the key from the original page, the second 135 * unpins the original page. In the first loop, dirty1 is set if 136 * the original page is modified, and dirty2 is set if any subsequent 137 * pages are modified. In the second loop, dirty1 starts off set if 138 * the original page has been modified, and is set if any subsequent 139 * pages are modified. 140 * 141 * If find the key referenced by the cursor, don't delete it, just 142 * flag it for future deletion. The cursor page number is P_INVALID 143 * unless the sequential scan is initialized, so no reason to check. 144 * A special case is when the already deleted cursor record was the 145 * only record found. If so, then the delete opertion fails as no 146 * records were deleted. 147 * 148 * Cycle in place in the current page until the current record doesn't 149 * match the key or the page is empty. If the latter, walk forward, 150 * skipping empty pages and repeating until a record doesn't match 151 * the key or the end of the tree is reached. 152 */ 153 cpgno = t->bt_bcursor.pgno; 154 cindex = t->bt_bcursor.index; 155 save = *e; 156 dirty1 = 0; 157 for (h = e->page, deleted = 0;;) { 158 dirty2 = 0; 159 do { 160 if (h->pgno == cpgno && e->index == cindex) { 161 if (!ISSET(t, B_DELCRSR)) { 162 SET(t, B_DELCRSR); 163 deleted = 1; 164 } 165 ++e->index; 166 } else { 167 if (__bt_dleaf(t, h, e->index)) { 168 if (h->pgno != save.page->pgno) 169 mpool_put(t->bt_mp, h, dirty2); 170 mpool_put(t->bt_mp, save.page, dirty1); 171 return (RET_ERROR); 172 } 173 if (h->pgno == save.page->pgno) 174 dirty1 = MPOOL_DIRTY; 175 else 176 dirty2 = MPOOL_DIRTY; 177 deleted = 1; 178 } 179 } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); 180 181 /* 182 * Quit if didn't find a match, no next page, or first key on 183 * the next page doesn't match. Don't unpin the original page 184 * unless an error occurs. 185 */ 186 if (e->index < NEXTINDEX(h)) 187 break; 188 for (;;) { 189 if ((pg = h->nextpg) == P_INVALID) 190 goto done1; 191 if (h->pgno != save.page->pgno) 192 mpool_put(t->bt_mp, h, dirty2); 193 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) { 194 mpool_put(t->bt_mp, save.page, dirty1); 195 return (RET_ERROR); 196 } 197 if (NEXTINDEX(h) != 0) { 198 e->page = h; 199 e->index = 0; 200 break; 201 } 202 } 203 204 if (__bt_cmp(t, key, e) != 0) 205 break; 206 } 207 208 /* 209 * Reach here with the original page and the last page referenced 210 * pinned (they may be the same). Release it if not the original. 211 */ 212 done1: if (h->pgno != save.page->pgno) 213 mpool_put(t->bt_mp, h, dirty2); 214 215 /* 216 * Walk backwards from the record previous to the record returned by 217 * __bt_search, skipping empty pages, until a record doesn't match 218 * the key or reach the beginning of the tree. 219 */ 220 *e = save; 221 for (;;) { 222 if (e->index) 223 --e->index; 224 for (h = e->page; e->index; --e->index) { 225 if (__bt_cmp(t, key, e) != 0) 226 goto done2; 227 if (h->pgno == cpgno && e->index == cindex) { 228 if (!ISSET(t, B_DELCRSR)) { 229 SET(t, B_DELCRSR); 230 deleted = 1; 231 } 232 } else { 233 if (__bt_dleaf(t, h, e->index) == RET_ERROR) { 234 mpool_put(t->bt_mp, h, dirty1); 235 return (RET_ERROR); 236 } 237 if (h->pgno == save.page->pgno) 238 dirty1 = MPOOL_DIRTY; 239 deleted = 1; 240 } 241 } 242 243 if ((pg = h->prevpg) == P_INVALID) 244 goto done2; 245 mpool_put(t->bt_mp, h, dirty1); 246 dirty1 = 0; 247 if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL) 248 return (RET_ERROR); 249 e->index = NEXTINDEX(e->page); 250 } 251 252 /* 253 * Reach here with the last page that was looked at pinned. Release 254 * it. 255 */ 256 done2: mpool_put(t->bt_mp, h, dirty1); 257 return (deleted ? RET_SUCCESS : RET_SPECIAL); 258 } 259 260 /* 261 * __BT_DLEAF -- Delete a single record from a leaf page. 262 * 263 * Parameters: 264 * t: tree 265 * index: index on current page to delete 266 * 267 * Returns: 268 * RET_SUCCESS, RET_ERROR. 269 */ 270 int 271 __bt_dleaf(t, h, index) 272 BTREE *t; 273 PAGE *h; 274 int index; 275 { 276 register BLEAF *bl; 277 register indx_t *ip, offset; 278 register size_t nbytes; 279 register int cnt; 280 char *from; 281 void *to; 282 283 /* 284 * Delete a record from a btree leaf page. Internal records are never 285 * deleted from internal pages, regardless of the records that caused 286 * them to be added being deleted. Pages made empty by deletion are 287 * not reclaimed. They are, however, made available for reuse. 288 * 289 * Pack the remaining entries at the end of the page, shift the indices 290 * down, overwriting the deleted record and its index. If the record 291 * uses overflow pages, make them available for reuse. 292 */ 293 to = bl = GETBLEAF(h, index); 294 if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) 295 return (RET_ERROR); 296 if (bl->flags & P_BIGDATA && 297 __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) 298 return (RET_ERROR); 299 nbytes = NBLEAF(bl); 300 301 /* 302 * Compress the key/data pairs. Compress and adjust the [BR]LEAF 303 * offsets. Reset the headers. 304 */ 305 from = (char *)h + h->upper; 306 memmove(from + nbytes, from, (char *)to - from); 307 h->upper += nbytes; 308 309 offset = h->linp[index]; 310 for (cnt = index, ip = &h->linp[0]; cnt--; ++ip) 311 if (ip[0] < offset) 312 ip[0] += nbytes; 313 for (cnt = NEXTINDEX(h) - index; --cnt; ++ip) 314 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 315 h->lower -= sizeof(indx_t); 316 return (RET_SUCCESS); 317 } 318