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