lib/libc/db/btree/bt_delete.c

   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.8 2005/11/12 23:01:54 swildner 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(const DB *dbp, const DBT *key, u_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 = 0;
 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         u_int32_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, u_int idx)
 460 {
 461         BLEAF *bl;
 462         indx_t cnt, *ip, offset;
 463         u_int32_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, u_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 }