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