lib/libc/db/btree/bt_delete.c

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