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 * 3. 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 * @(#)bt_delete.c 8.13 (Berkeley) 7/28/94 33 * $DragonFly: src/lib/libc/db/btree/bt_delete.c,v 1.7 2005/09/19 09:20:37 asmodai Exp $ 34 */ 35 36 #include <sys/types.h> 37 38 #include <errno.h> 39 #include <stdio.h> 40 #include <string.h> 41 42 #include <db.h> 43 #include "btree.h" 44 45 static int __bt_bdelete (BTREE *, const DBT *); 46 static int __bt_curdel (BTREE *, const DBT *, PAGE *, u_int); 47 static int __bt_pdelete (BTREE *, PAGE *); 48 static int __bt_relink (BTREE *, PAGE *); 49 static int __bt_stkacq (BTREE *, PAGE **, CURSOR *); 50 51 /* 52 * __bt_delete 53 * Delete the item(s) referenced by a key. 54 * 55 * Return RET_SPECIAL if the key is not found. 56 */ 57 int 58 __bt_delete(dbp, key, flags) 59 const DB *dbp; 60 const DBT *key; 61 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 */ 138 static int 139 __bt_stkacq(t, hp, c) 140 BTREE *t; 141 PAGE **hp; 142 CURSOR *c; 143 { 144 BINTERNAL *bi; 145 EPG *e; 146 EPGNO *parent; 147 PAGE *h; 148 indx_t idx = 0; 149 pgno_t pgno; 150 recno_t nextpg, prevpg; 151 int exact, level; 152 153 /* 154 * Find the first occurrence of the key in the tree. Toss the 155 * currently locked page so we don't hit an already-locked page. 156 */ 157 h = *hp; 158 mpool_put(t->bt_mp, h, 0); 159 if ((e = __bt_search(t, &c->key, &exact)) == NULL) 160 return (1); 161 h = e->page; 162 163 /* See if we got it in one shot. */ 164 if (h->pgno == c->pg.pgno) 165 goto ret; 166 167 /* 168 * Move right, looking for the page. At each move we have to move 169 * up the stack until we don't have to move to the next page. If 170 * we have to change pages at an internal level, we have to fix the 171 * stack back up. 172 */ 173 while (h->pgno != c->pg.pgno) { 174 if ((nextpg = h->nextpg) == P_INVALID) 175 break; 176 mpool_put(t->bt_mp, h, 0); 177 178 /* Move up the stack. */ 179 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 180 /* Get the parent page. */ 181 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 182 return (1); 183 184 /* Move to the next index. */ 185 if (parent->index != NEXTINDEX(h) - 1) { 186 idx = parent->index + 1; 187 BT_PUSH(t, h->pgno, idx); 188 break; 189 } 190 mpool_put(t->bt_mp, h, 0); 191 } 192 193 /* Restore the stack. */ 194 while (level--) { 195 /* Push the next level down onto the stack. */ 196 bi = GETBINTERNAL(h, idx); 197 pgno = bi->pgno; 198 BT_PUSH(t, pgno, 0); 199 200 /* Lose the currently pinned page. */ 201 mpool_put(t->bt_mp, h, 0); 202 203 /* Get the next level down. */ 204 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 205 return (1); 206 idx = 0; 207 } 208 mpool_put(t->bt_mp, h, 0); 209 if ((h = mpool_get(t->bt_mp, nextpg, 0)) == NULL) 210 return (1); 211 } 212 213 if (h->pgno == c->pg.pgno) 214 goto ret; 215 216 /* Reacquire the original stack. */ 217 mpool_put(t->bt_mp, h, 0); 218 if ((e = __bt_search(t, &c->key, &exact)) == NULL) 219 return (1); 220 h = e->page; 221 222 /* 223 * Move left, looking for the page. At each move we have to move 224 * up the stack until we don't have to change pages to move to the 225 * next page. If we have to change pages at an internal level, we 226 * have to fix the stack back up. 227 */ 228 while (h->pgno != c->pg.pgno) { 229 if ((prevpg = h->prevpg) == P_INVALID) 230 break; 231 mpool_put(t->bt_mp, h, 0); 232 233 /* Move up the stack. */ 234 for (level = 0; (parent = BT_POP(t)) != NULL; ++level) { 235 /* Get the parent page. */ 236 if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 237 return (1); 238 239 /* Move to the next index. */ 240 if (parent->index != 0) { 241 idx = parent->index - 1; 242 BT_PUSH(t, h->pgno, idx); 243 break; 244 } 245 mpool_put(t->bt_mp, h, 0); 246 } 247 248 /* Restore the stack. */ 249 while (level--) { 250 /* Push the next level down onto the stack. */ 251 bi = GETBINTERNAL(h, idx); 252 pgno = bi->pgno; 253 254 /* Lose the currently pinned page. */ 255 mpool_put(t->bt_mp, h, 0); 256 257 /* Get the next level down. */ 258 if ((h = mpool_get(t->bt_mp, pgno, 0)) == NULL) 259 return (1); 260 261 idx = NEXTINDEX(h) - 1; 262 BT_PUSH(t, pgno, idx); 263 } 264 mpool_put(t->bt_mp, h, 0); 265 if ((h = mpool_get(t->bt_mp, prevpg, 0)) == NULL) 266 return (1); 267 } 268 269 270 ret: mpool_put(t->bt_mp, h, 0); 271 return ((*hp = mpool_get(t->bt_mp, c->pg.pgno, 0)) == NULL); 272 } 273 274 /* 275 * __bt_bdelete -- 276 * Delete all key/data pairs matching the specified key. 277 * 278 * Parameters: 279 * t: tree 280 * key: key to delete 281 * 282 * Returns: 283 * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. 284 */ 285 static int 286 __bt_bdelete(t, key) 287 BTREE *t; 288 const DBT *key; 289 { 290 EPG *e; 291 PAGE *h; 292 int deleted, exact, redo; 293 294 deleted = 0; 295 296 /* Find any matching record; __bt_search pins the page. */ 297 loop: if ((e = __bt_search(t, key, &exact)) == NULL) 298 return (deleted ? RET_SUCCESS : RET_ERROR); 299 if (!exact) { 300 mpool_put(t->bt_mp, e->page, 0); 301 return (deleted ? RET_SUCCESS : RET_SPECIAL); 302 } 303 304 /* 305 * Delete forward, then delete backward, from the found key. If 306 * there are duplicates and we reach either side of the page, do 307 * the key search again, so that we get them all. 308 */ 309 redo = 0; 310 h = e->page; 311 do { 312 if (__bt_dleaf(t, key, h, e->index)) { 313 mpool_put(t->bt_mp, h, 0); 314 return (RET_ERROR); 315 } 316 if (F_ISSET(t, B_NODUPS)) { 317 if (NEXTINDEX(h) == 0) { 318 if (__bt_pdelete(t, h)) 319 return (RET_ERROR); 320 } else 321 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 322 return (RET_SUCCESS); 323 } 324 deleted = 1; 325 } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); 326 327 /* Check for right-hand edge of the page. */ 328 if (e->index == NEXTINDEX(h)) 329 redo = 1; 330 331 /* Delete from the key to the beginning of the page. */ 332 while (e->index-- > 0) { 333 if (__bt_cmp(t, key, e) != 0) 334 break; 335 if (__bt_dleaf(t, key, h, e->index) == RET_ERROR) { 336 mpool_put(t->bt_mp, h, 0); 337 return (RET_ERROR); 338 } 339 if (e->index == 0) 340 redo = 1; 341 } 342 343 /* Check for an empty page. */ 344 if (NEXTINDEX(h) == 0) { 345 if (__bt_pdelete(t, h)) 346 return (RET_ERROR); 347 goto loop; 348 } 349 350 /* Put the page. */ 351 mpool_put(t->bt_mp, h, MPOOL_DIRTY); 352 353 if (redo) 354 goto loop; 355 return (RET_SUCCESS); 356 } 357 358 /* 359 * __bt_pdelete -- 360 * Delete a single page from the tree. 361 * 362 * Parameters: 363 * t: tree 364 * h: leaf page 365 * 366 * Returns: 367 * RET_SUCCESS, RET_ERROR. 368 * 369 * Side-effects: 370 * mpool_put's the page 371 */ 372 static int 373 __bt_pdelete(t, h) 374 BTREE *t; 375 PAGE *h; 376 { 377 BINTERNAL *bi; 378 PAGE *pg; 379 EPGNO *parent; 380 indx_t cnt, idx, *ip, offset; 381 u_int32_t nksize; 382 char *from; 383 384 /* 385 * Walk the parent page stack -- a LIFO stack of the pages that were 386 * traversed when we searched for the page where the delete occurred. 387 * Each stack entry is a page number and a page index offset. The 388 * offset is for the page traversed on the search. We've just deleted 389 * a page, so we have to delete the key from the parent page. 390 * 391 * If the delete from the parent page makes it empty, this process may 392 * continue all the way up the tree. We stop if we reach the root page 393 * (which is never deleted, it's just not worth the effort) or if the 394 * delete does not empty the page. 395 */ 396 while ((parent = BT_POP(t)) != NULL) { 397 /* Get the parent page. */ 398 if ((pg = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) 399 return (RET_ERROR); 400 401 idx = parent->index; 402 bi = GETBINTERNAL(pg, idx); 403 404 /* Free any overflow pages. */ 405 if (bi->flags & P_BIGKEY && 406 __ovfl_delete(t, bi->bytes) == RET_ERROR) { 407 mpool_put(t->bt_mp, pg, 0); 408 return (RET_ERROR); 409 } 410 411 /* 412 * Free the parent if it has only the one key and it's not the 413 * root page. If it's the rootpage, turn it back into an empty 414 * leaf page. 415 */ 416 if (NEXTINDEX(pg) == 1) 417 if (pg->pgno == P_ROOT) { 418 pg->lower = BTDATAOFF; 419 pg->upper = t->bt_psize; 420 pg->flags = P_BLEAF; 421 } else { 422 if (__bt_relink(t, pg) || __bt_free(t, pg)) 423 return (RET_ERROR); 424 continue; 425 } 426 else { 427 /* Pack remaining key items at the end of the page. */ 428 nksize = NBINTERNAL(bi->ksize); 429 from = (char *)pg + pg->upper; 430 memmove(from + nksize, from, (char *)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 */ 468 int 469 __bt_dleaf(BTREE *t, const DBT *key, PAGE *h, u_int idx) 470 { 471 BLEAF *bl; 472 indx_t cnt, *ip, offset; 473 u_int32_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 *)h + h->upper; 495 memmove(from + nbytes, from, (char *)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 */ 529 static 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); 598 dup1: mpool_put(t->bt_mp, pg, 0); 599 dup2: 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 */ 624 static int 625 __bt_relink(t, h) 626 BTREE *t; 627 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