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