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