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