lib/libc/db/btree/bt_delete.c

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