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