1 /* $NetBSD: bt_delete.c,v 1.13 2007/02/03 23:46:09 christos 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. Neither the name of the University nor the names of its contributors 19 * may be used to endorse or promote products derived from this software 20 * without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include <sys/cdefs.h> 36 #if defined(LIBC_SCCS) && !defined(lint) 37 #if 0 38 static char sccsid[] = "@(#)bt_delete.c 8.13 (Berkeley) 7/28/94"; 39 #else 40 __RCSID("$NetBSD: bt_delete.c,v 1.13 2007/02/03 23:46:09 christos Exp $"); 41 #endif 42 #endif /* LIBC_SCCS and not lint */ 43 44 #include "namespace.h" 45 #include <sys/types.h> 46 47 #include <assert.h> 48 #include <errno.h> 49 #include <stdio.h> 50 #include <string.h> 51 52 #include <db.h> 53 #include "btree.h" 54 55 static int __bt_bdelete(BTREE *, const DBT *); 56 static int __bt_curdel(BTREE *, const DBT *, PAGE *, u_int); 57 static int __bt_pdelete(BTREE *, PAGE *); 58 static int __bt_relink(BTREE *, PAGE *); 59 static int __bt_stkacq(BTREE *, PAGE **, CURSOR *); 60 61 /* 62 * __bt_delete 63 * Delete the item(s) referenced by a key. 64 * 65 * Return RET_SPECIAL if the key is not found. 66 */ 67 int 68 __bt_delete(const DB *dbp, const DBT *key, u_int flags) 69 { 70 BTREE *t; 71 CURSOR *c; 72 PAGE *h; 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 /* Check for change to a read-only tree. */ 84 if (F_ISSET(t, B_RDONLY)) { 85 errno = EPERM; 86 return (RET_ERROR); 87 } 88 89 switch (flags) { 90 case 0: 91 status = __bt_bdelete(t, key); 92 break; 93 case R_CURSOR: 94 /* 95 * If flags is R_CURSOR, delete the cursor. Must already 96 * have started a scan and not have already deleted it. 97 */ 98 c = &t->bt_cursor; 99 if (F_ISSET(c, CURS_INIT)) { 100 if (F_ISSET(c, CURS_ACQUIRE | CURS_AFTER | CURS_BEFORE)) 101 return (RET_SPECIAL); 102 if ((h = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL) 103 return (RET_ERROR); 104 105 /* 106 * If the page is about to be emptied, we'll need to 107 * delete it, which means we have to acquire a stack. 108 */ 109 if (NEXTINDEX(h) == 1) 110 if (__bt_stkacq(t, &h, &t->bt_cursor)) 111 return (RET_ERROR); 112 113 status = __bt_dleaf(t, NULL, h, (u_int)c->pg.index); 114 115 if (NEXTINDEX(h) == 0 && status == RET_SUCCESS) { 116 if (__bt_pdelete(t, h)) 117 return (RET_ERROR); 118 } else 119 mpool_put(t->bt_mp, h, 120 (u_int)(status == RET_SUCCESS ? 121 MPOOL_DIRTY : 0)); 122 break; 123 } 124 /* FALLTHROUGH */ 125 default: 126 errno = EINVAL; 127 return (RET_ERROR); 128 } 129 if (status == RET_SUCCESS) 130 F_SET(t, B_MODIFIED); 131 return (status); 132 } 133 134 /* 135 * __bt_stkacq -- 136 * Acquire a stack so we can delete a cursor entry. 137 * 138 * Parameters: 139 * t: tree 140 * hp: pointer to current, pinned PAGE pointer 141 * c: pointer to the cursor 142 * 143 * Returns: 144 * 0 on success, 1 on failure 145 */ 146 static int 147 __bt_stkacq(BTREE *t, PAGE **hp, CURSOR *c) 148 { 149 BINTERNAL *bi; 150 EPG *e; 151 EPGNO *parent; 152 PAGE *h; 153 indx_t idx = 0; /* Pacify gcc */ 154 pgno_t pgno; 155 recno_t nextpg, prevpg; 156 int exact, level; 157 158 /* 159 * Find the first occurrence of the key in the tree. Toss the 160 * currently locked page so we don't hit an already-locked page. 161 */ 162 h = *hp; 163 mpool_put(t->bt_mp, h, 0); 164 if ((e = __bt_search(t, &c->key, &exact)) == NULL) 165 return (1); 166 h = e->page; 167 168 /* See if we got it in one shot. */ 169 if (h->pgno == c->pg.pgno) 170 goto ret; 171 172 /* 173 * Move right, looking for the page. At each move we have to move 174 * up the stack until we don't have to move to the next page. If 175 * we have to change pages at an internal level, we have to fix the 176 * stack back up. 177 */ 178 while (h->pgno != c->pg.pgno) { 179 if ((nextpg = h->nextpg) == P_INVALID) 180 break; 181 mpool_put(t->bt_mp, h, 0); 182 183 /* Move up the stack. */ 184 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 185 /* Get the parent page. */ 186 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 187 return (1); 188 189 /* Move to the next index. */ 190 if (parent->index != NEXTINDEX(h) - 1) { 191 idx = parent->index + 1; 192 BT_PUSH(t, h->pgno, idx); 193 break; 194 } 195 mpool_put(t->bt_mp, h, 0); 196 } 197 198 /* Restore the stack. */ 199 while (level--) { 200 /* Push the next level down onto the stack. */ 201 bi = GETBINTERNAL(h, idx); 202 pgno = bi->pgno; 203 BT_PUSH(t, pgno, 0); 204 205 /* Lose the currently pinned page. */ 206 mpool_put(t->bt_mp, h, 0); 207 208 /* Get the next level down. */ 209 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 210 return (1); 211 idx = 0; 212 } 213 mpool_put(t->bt_mp, h, 0); 214 if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL) 215 return (1); 216 } 217 218 if (h->pgno == c->pg.pgno) 219 goto ret; 220 221 /* Reacquire the original stack. */ 222 mpool_put(t->bt_mp, h, 0); 223 if ((e = __bt_search(t, &c->key, &exact)) == NULL) 224 return (1); 225 h = e->page; 226 227 /* 228 * Move left, looking for the page. At each move we have to move 229 * up the stack until we don't have to change pages to move to the 230 * next page. If we have to change pages at an internal level, we 231 * have to fix the stack back up. 232 */ 233 while (h->pgno != c->pg.pgno) { 234 if ((prevpg = h->prevpg) == P_INVALID) 235 break; 236 mpool_put(t->bt_mp, h, 0); 237 238 /* Move up the stack. */ 239 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 240 /* Get the parent page. */ 241 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 242 return (1); 243 244 /* Move to the next index. */ 245 if (parent->index != 0) { 246 idx = parent->index - 1; 247 BT_PUSH(t, h->pgno, idx); 248 break; 249 } 250 mpool_put(t->bt_mp, h, 0); 251 } 252 253 /* Restore the stack. */ 254 while (level--) { 255 /* Push the next level down onto the stack. */ 256 bi = GETBINTERNAL(h, idx); 257 pgno = bi->pgno; 258 259 /* Lose the currently pinned page. */ 260 mpool_put(t->bt_mp, h, 0); 261 262 /* Get the next level down. */ 263 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 264 return (1); 265 266 idx = NEXTINDEX(h) - 1; 267 BT_PUSH(t, pgno, idx); 268 } 269 mpool_put(t->bt_mp, h, 0); 270 if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL) 271 return (1); 272 } 273 274 275 ret: mpool_put(t->bt_mp, h, 0); 276 return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL); 277 } 278 279 /* 280 * __bt_bdelete -- 281 * Delete all key/data pairs matching the specified key. 282 * 283 * Parameters: 284 * t: tree 285 * key: key to delete 286 * 287 * Returns: 288 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 289 */ 290 static int 291 __bt_bdelete(BTREE *t, const DBT *key) 292 { 293 EPG *e; 294 PAGE *h; 295 int deleted, exact, redo; 296 297 deleted = 0; 298 299 /* Find any matching record; __bt_search pins the page. */ 300 loop: if ((e = __bt_search(t, key, &exact)) == NULL) 301 return (deleted ? RET_SUCCESS : RET_ERROR); 302 if (!exact) { 303 mpool_put(t->bt_mp, e->page, 0); 304 return (deleted ? RET_SUCCESS : RET_SPECIAL); 305 } 306 307 /* 308 * Delete forward, then delete backward, from the found key. If 309 * there are duplicates and we reach either side of the page, do 310 * the key search again, so that we get them all. 311 */ 312 redo = 0; 313 h = e->page; 314 do { 315 if (__bt_dleaf(t, key, h, (u_int)e->index)) { 316 mpool_put(t->bt_mp, h, 0); 317 return (RET_ERROR); 318 } 319 if (F_ISSET(t, B_NODUPS)) { 320 if (NEXTINDEX(h) == 0) { 321 if (__bt_pdelete(t, h)) 322 return (RET_ERROR); 323 } else 324 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 325 return (RET_SUCCESS); 326 } 327 deleted = 1; 328 } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); 329 330 /* Check for right-hand edge of the page. */ 331 if (e->index == NEXTINDEX(h)) 332 redo = 1; 333 334 /* Delete from the key to the beginning of the page. */ 335 while (e->index-- > 0) { 336 if (__bt_cmp(t, key, e) != 0) 337 break; 338 if (__bt_dleaf(t, key, h, (u_int)e->index) == RET_ERROR) { 339 mpool_put(t->bt_mp, h, 0); 340 return (RET_ERROR); 341 } 342 if (e->index == 0) 343 redo = 1; 344 } 345 346 /* Check for an empty page. */ 347 if (NEXTINDEX(h) == 0) { 348 if (__bt_pdelete(t, h)) 349 return (RET_ERROR); 350 goto loop; 351 } 352 353 /* Put the page. */ 354 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 355 356 if (redo) 357 goto loop; 358 return (RET_SUCCESS); 359 } 360 361 /* 362 * __bt_pdelete -- 363 * Delete a single page from the tree. 364 * 365 * Parameters: 366 * t: tree 367 * h: leaf page 368 * 369 * Returns: 370 * RET_SUCCESS, RET_ERROR. 371 * 372 * Side-effects: 373 * mpool_put's the page 374 */ 375 static int 376 __bt_pdelete(BTREE *t, PAGE *h) 377 { 378 BINTERNAL *bi; 379 PAGE *pg; 380 EPGNO *parent; 381 indx_t cnt, idx, *ip, offset; 382 u_int32_t nksize; 383 char *from; 384 385 /* 386 * Walk the parent page stack -- a LIFO stack of the pages that were 387 * traversed when we searched for the page where the delete occurred. 388 * Each stack entry is a page number and a page index offset. The 389 * offset is for the page traversed on the search. We've just deleted 390 * a page, so we have to delete the key from the parent page. 391 * 392 * If the delete from the parent page makes it empty, this process may 393 * continue all the way up the tree. We stop if we reach the root page 394 * (which is never deleted, it's just not worth the effort) or if the 395 * delete does not empty the page. 396 */ 397 while ((parent = BT_POP(t)) != NULL) { 398 /* Get the parent page. */ 399 if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 400 return (RET_ERROR); 401 402 idx = parent->index; 403 bi = GETBINTERNAL(pg, idx); 404 405 /* Free any overflow pages. */ 406 if (bi->flags & P_BIGKEY && 407 __ovfl_delete(t, bi->bytes) == RET_ERROR) { 408 mpool_put(t->bt_mp, pg, 0); 409 return (RET_ERROR); 410 } 411 412 /* 413 * Free the parent if it has only the one key and it's not the 414 * root page. If it's the rootpage, turn it back into an empty 415 * leaf page. 416 */ 417 if (NEXTINDEX(pg) == 1) { 418 if (pg->pgno == P_ROOT) { 419 pg->lower = BTDATAOFF; 420 pg->upper = t->bt_psize; 421 pg->flags = P_BLEAF; 422 } else { 423 if (__bt_relink(t, pg) || __bt_free(t, pg)) 424 return (RET_ERROR); 425 continue; 426 } 427 } else { 428 /* Pack remaining key items at the end of the page. */ 429 nksize = NBINTERNAL(bi->ksize); 430 from = (char *)(void *)pg + pg->upper; 431 memmove(from + nksize, from, 432 (size_t)((char *)(void *)bi - from)); 433 pg->upper += nksize; 434 435 /* Adjust indices' offsets, shift the indices down. */ 436 offset = pg->linp[idx]; 437 for (cnt = idx, ip = &pg->linp[0]; cnt--; ++ip) 438 if (ip[0] < offset) 439 ip[0] += nksize; 440 for (cnt = NEXTINDEX(pg) - idx; --cnt; ++ip) 441 ip[0] = ip[1] < offset ? ip[1] + nksize : ip[1]; 442 pg->lower -= sizeof(indx_t); 443 } 444 445 mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 446 break; 447 } 448 449 /* Free the leaf page, as long as it wasn't the root. */ 450 if (h->pgno == P_ROOT) { 451 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 452 return (RET_SUCCESS); 453 } 454 return (__bt_relink(t, h) || __bt_free(t, h)); 455 } 456 457 /* 458 * __bt_dleaf -- 459 * Delete a single record from a leaf page. 460 * 461 * Parameters: 462 * t: tree 463 * key: referenced key 464 * h: page 465 * idx: index on page to delete 466 * 467 * Returns: 468 * RET_SUCCESS, RET_ERROR. 469 */ 470 int 471 __bt_dleaf(BTREE *t, const DBT *key, PAGE *h, u_int idx) 472 { 473 BLEAF *bl; 474 indx_t cnt, *ip, offset; 475 u_int32_t nbytes; 476 void *to; 477 char *from; 478 479 /* If this record is referenced by the cursor, delete the cursor. */ 480 if (F_ISSET(&t->bt_cursor, CURS_INIT) && 481 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 482 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index == idx && 483 __bt_curdel(t, key, h, idx)) 484 return (RET_ERROR); 485 486 /* If the entry uses overflow pages, make them available for reuse. */ 487 to = bl = GETBLEAF(h, idx); 488 if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) 489 return (RET_ERROR); 490 if (bl->flags & P_BIGDATA && 491 __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) 492 return (RET_ERROR); 493 494 /* Pack the remaining key/data items at the end of the page. */ 495 nbytes = NBLEAF(bl); 496 from = (char *)(void *)h + h->upper; 497 memmove(from + nbytes, from, (size_t)((char *)(void *)to - from)); 498 h->upper += nbytes; 499 500 /* Adjust the indices' offsets, shift the indices down. */ 501 offset = h->linp[idx]; 502 for (cnt = idx, ip = &h->linp[0]; cnt--; ++ip) 503 if (ip[0] < offset) 504 ip[0] += nbytes; 505 for (cnt = NEXTINDEX(h) - idx; --cnt; ++ip) 506 ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; 507 h->lower -= sizeof(indx_t); 508 509 /* If the cursor is on this page, adjust it as necessary. */ 510 if (F_ISSET(&t->bt_cursor, CURS_INIT) && 511 !F_ISSET(&t->bt_cursor, CURS_ACQUIRE) && 512 t->bt_cursor.pg.pgno == h->pgno && t->bt_cursor.pg.index > idx) 513 --t->bt_cursor.pg.index; 514 515 return (RET_SUCCESS); 516 } 517 518 /* 519 * __bt_curdel -- 520 * Delete the cursor. 521 * 522 * Parameters: 523 * t: tree 524 * key: referenced key (or NULL) 525 * h: page 526 * idx: index on page to delete 527 * 528 * Returns: 529 * RET_SUCCESS, RET_ERROR. 530 */ 531 static int 532 __bt_curdel(BTREE *t, const DBT *key, PAGE *h, u_int idx) 533 { 534 CURSOR *c; 535 EPG e; 536 PAGE *pg; 537 int curcopy, status; 538 539 /* 540 * If there are duplicates, move forward or backward to one. 541 * Otherwise, copy the key into the cursor area. 542 */ 543 c = &t->bt_cursor; 544 F_CLR(c, CURS_AFTER | CURS_BEFORE | CURS_ACQUIRE); 545 546 curcopy = 0; 547 if (!F_ISSET(t, B_NODUPS)) { 548 /* 549 * We're going to have to do comparisons. If we weren't 550 * provided a copy of the key, i.e. the user is deleting 551 * the current cursor position, get one. 552 */ 553 if (key == NULL) { 554 e.page = h; 555 e.index = idx; 556 if ((status = __bt_ret(t, &e, 557 &c->key, &c->key, NULL, NULL, 1)) != RET_SUCCESS) 558 return (status); 559 curcopy = 1; 560 key = &c->key; 561 } 562 /* Check previous key, if not at the beginning of the page. */ 563 if (idx > 0) { 564 e.page = h; 565 e.index = idx - 1; 566 if (__bt_cmp(t, key, &e) == 0) { 567 F_SET(c, CURS_BEFORE); 568 goto dup2; 569 } 570 } 571 /* Check next key, if not at the end of the page. */ 572 if (idx < NEXTINDEX(h) - 1) { 573 e.page = h; 574 e.index = idx + 1; 575 if (__bt_cmp(t, key, &e) == 0) { 576 F_SET(c, CURS_AFTER); 577 goto dup2; 578 } 579 } 580 /* Check previous key if at the beginning of the page. */ 581 if (idx == 0 && h->prevpg != P_INVALID) { 582 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) 583 return (RET_ERROR); 584 e.page = pg; 585 e.index = NEXTINDEX(pg) - 1; 586 if (__bt_cmp(t, key, &e) == 0) { 587 F_SET(c, CURS_BEFORE); 588 goto dup1; 589 } 590 mpool_put(t->bt_mp, pg, 0); 591 } 592 /* Check next key if at the end of the page. */ 593 if (idx == NEXTINDEX(h) - 1 && h->nextpg != P_INVALID) { 594 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) 595 return (RET_ERROR); 596 e.page = pg; 597 e.index = 0; 598 if (__bt_cmp(t, key, &e) == 0) { 599 F_SET(c, CURS_AFTER); 600 dup1: mpool_put(t->bt_mp, pg, 0); 601 dup2: c->pg.pgno = e.page->pgno; 602 c->pg.index = e.index; 603 return (RET_SUCCESS); 604 } 605 mpool_put(t->bt_mp, pg, 0); 606 } 607 } 608 e.page = h; 609 e.index = idx; 610 if (curcopy || (status = 611 __bt_ret(t, &e, &c->key, &c->key, NULL, NULL, 1)) == RET_SUCCESS) { 612 F_SET(c, CURS_ACQUIRE); 613 return (RET_SUCCESS); 614 } 615 return (status); 616 } 617 618 /* 619 * __bt_relink -- 620 * Link around a deleted page. 621 * 622 * Parameters: 623 * t: tree 624 * h: page to be deleted 625 */ 626 static int 627 __bt_relink(BTREE *t, PAGE *h) 628 { 629 PAGE *pg; 630 631 if (h->nextpg != P_INVALID) { 632 if ((pg = mpool_get(t->bt_mp, h->nextpg, 0)) == NULL) 633 return (RET_ERROR); 634 pg->prevpg = h->prevpg; 635 mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 636 } 637 if (h->prevpg != P_INVALID) { 638 if ((pg = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) 639 return (RET_ERROR); 640 pg->nextpg = h->nextpg; 641 mpool_put(t->bt_mp, pg, MPOOL_DIRTY); 642 } 643 return (0); 644 } 645