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