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