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