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