db2/btree/bt_cursor.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1996, 1997
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7
   8 #include "config.h"
   9
  10 #ifndef lint
  11 static const char sccsid[] = "@(#)bt_cursor.c   10.33 (Sleepycat) 9/24/97";
  12 #endif /* not lint */
  13
  14 #ifndef NO_SYSTEM_INCLUDES
  15 #include <sys/types.h>
  16
  17 #include <errno.h>
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #endif
  22
  23 #include "db_int.h"
  24 #include "db_page.h"
  25 #include "btree.h"
  26
  27 static int __bam_c_close __P((DBC *));
  28 static int __bam_c_del __P((DBC *, int));
  29 static int __bam_c_first __P((DB *, CURSOR *));
  30 static int __bam_c_get __P((DBC *, DBT *, DBT *, int));
  31 static int __bam_c_last __P((DB *, CURSOR *));
  32 static int __bam_c_next __P((DB *, CURSOR *, int));
  33 static int __bam_c_physdel __P((DB *, CURSOR *, PAGE *));
  34 static int __bam_c_prev __P((DB *, CURSOR *));
  35 static int __bam_c_put __P((DBC *, DBT *, DBT *, int));
  36 static int __bam_c_rget __P((DB *, CURSOR *, DBT *, DBT *, int));
  37 static int __bam_c_search __P((DB *, CURSOR *, const DBT *, u_int, int, int *));
  38
  39 /* Discard the current page/lock held by a cursor. */
  40 #undef  DISCARD
  41 #define DISCARD(dbp, cp) {                                              \
  42         (void)memp_fput(dbp->mpf, (cp)->page, 0);                       \
  43         (cp)->page = NULL;                                              \
  44         (void)__BT_TLPUT((dbp), (cp)->lock);                            \
  45         (cp)->lock = LOCK_INVALID;                                      \
  46 }
  47
  48 /*
  49  * __bam_cursor --
  50  *      Interface to the cursor functions.
  51  *
  52  * PUBLIC: int __bam_cursor __P((DB *, DB_TXN *, DBC **));
  53  */
  54 int
  55 __bam_cursor(dbp, txn, dbcp)
  56         DB *dbp;
  57         DB_TXN *txn;
  58         DBC **dbcp;
  59 {
  60         CURSOR *cp;
  61         DBC *dbc;
  62
  63         DEBUG_LWRITE(dbp, txn, "bam_cursor", NULL, NULL, 0);
  64
  65         if ((dbc = (DBC *)calloc(1, sizeof(DBC))) == NULL)
  66                 return (ENOMEM);
  67         if ((cp = (CURSOR *)calloc(1, sizeof(CURSOR))) == NULL) {
  68                 free(dbc);
  69                 return (ENOMEM);
  70         }
  71
  72         cp->dbc = dbc;
  73         cp->pgno = cp->dpgno = PGNO_INVALID;
  74         cp->lock = LOCK_INVALID;
  75
  76         dbc->dbp = dbp;
  77         dbc->txn = txn;
  78         dbc->internal = cp;
  79         dbc->c_close = __bam_c_close;
  80         dbc->c_del = __bam_c_del;
  81         dbc->c_get = __bam_c_get;
  82         dbc->c_put = __bam_c_put;
  83
  84         /*
  85          * All cursors are queued from the master DB structure.  Add the
  86          * cursor to that queue.
  87          */
  88         DB_THREAD_LOCK(dbp);
  89         TAILQ_INSERT_HEAD(&dbp->curs_queue, dbc, links);
  90         DB_THREAD_UNLOCK(dbp);
  91
  92         *dbcp = dbc;
  93         return (0);
  94 }
  95
  96 /*
  97  * __bam_c_close --
  98  *      Close a single cursor.
  99  */
 100 static int
 101 __bam_c_close(dbc)
 102         DBC *dbc;
 103 {
 104         DB *dbp;
 105         int ret;
 106
 107         DEBUG_LWRITE(dbc->dbp, dbc->txn, "bam_c_close", NULL, NULL, 0);
 108
 109         GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
 110
 111         ret = __bam_c_iclose(dbp, dbc);
 112
 113         PUTHANDLE(dbp);
 114         return (ret);
 115 }
 116
 117 /*
 118  * __bam_c_iclose --
 119  *      Close a single cursor -- internal version.
 120  *
 121  * PUBLIC: int __bam_c_iclose __P((DB *, DBC *));
 122  */
 123 int
 124 __bam_c_iclose(dbp, dbc)
 125         DB *dbp;
 126         DBC *dbc;
 127 {
 128         CURSOR *cp;
 129         int ret;
 130
 131         cp = dbc->internal;
 132
 133         /* If a cursor key was deleted, perform the actual deletion.  */
 134         ret = F_ISSET(cp, C_DELETED) ? __bam_c_physdel(dbp, cp, NULL) : 0;
 135
 136         /* Discard any lock if we're not inside a transaction. */
 137         if (cp->lock != LOCK_INVALID)
 138                 (void)__BT_TLPUT(dbp, cp->lock);
 139
 140         /*
 141          * All cursors are queued from the master DB structure.  Remove the
 142          * cursor from that queue.
 143          */
 144         DB_THREAD_LOCK(dbc->dbp);
 145         TAILQ_REMOVE(&dbc->dbp->curs_queue, dbc, links);
 146         DB_THREAD_UNLOCK(dbc->dbp);
 147
 148         /* Discard the structures. */
 149         FREE(dbc->internal, sizeof(CURSOR));
 150         FREE(dbc, sizeof(DBC));
 151
 152         return (ret);
 153 }
 154
 155 /*
 156  * __bam_c_del --
 157  *      Delete using a cursor.
 158  */
 159 static int
 160 __bam_c_del(dbc, flags)
 161         DBC *dbc;
 162         int flags;
 163 {
 164         CURSOR *cp;
 165         DB *dbp;
 166         DB_LOCK lock;
 167         PAGE *h;
 168         db_pgno_t pgno;
 169         db_indx_t indx;
 170         int ret;
 171
 172         DEBUG_LWRITE(dbc->dbp, dbc->txn, "bam_c_del", NULL, NULL, flags);
 173
 174         cp = dbc->internal;
 175
 176         /* Check for invalid flags. */
 177         if ((ret = __db_cdelchk(dbc->dbp, flags,
 178             F_ISSET(dbc->dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
 179                 return (ret);
 180
 181         /* If already deleted, return failure. */
 182         if (F_ISSET(cp, C_DELETED | C_REPLACE))
 183                 return (DB_KEYEMPTY);
 184
 185         GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
 186
 187         /*
 188          * We don't physically delete the record until the cursor moves,
 189          * so we have to have a long-lived write lock on the page instead
 190          * of a long-lived read lock.  Note, we have to have a read lock
 191          * to even get here, so we simply discard it.
 192          */
 193         if (F_ISSET(dbp, DB_AM_LOCKING) && cp->mode != DB_LOCK_WRITE) {
 194                 if ((ret = __bam_lget(dbp,
 195                     0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
 196                         goto err;
 197                 (void)__BT_TLPUT(dbp, cp->lock);
 198                 cp->lock = lock;
 199                 cp->mode = DB_LOCK_WRITE;
 200         }
 201
 202         /*
 203          * Acquire the underlying page (which may be different from the above
 204          * page because it may be a duplicate page), and set the on-page and
 205          * in-cursor delete flags.  We don't need to lock it as we've already
 206          * write-locked the page leading to it.
 207          */
 208         if (cp->dpgno == PGNO_INVALID) {
 209                 pgno = cp->pgno;
 210                 indx = cp->indx;
 211         } else {
 212                 pgno = cp->dpgno;
 213                 indx = cp->dindx;
 214         }
 215
 216         if ((ret = __bam_pget(dbp, &h, &pgno, 0)) != 0)
 217                 goto err;
 218
 219         /* Log the change. */
 220         if (DB_LOGGING(dbp) &&
 221             (ret = __bam_cdel_log(dbp->dbenv->lg_info, dbp->txn, &LSN(h),
 222             0, dbp->log_fileid, PGNO(h), &LSN(h), indx)) != 0) {
 223                 (void)memp_fput(dbp->mpf, h, 0);
 224                 goto err;
 225         }
 226
 227         /* Set the intent-to-delete flag on the page and in all cursors. */
 228         if (cp->dpgno == PGNO_INVALID)
 229                 B_DSET(GET_BKEYDATA(h, indx + O_INDX)->type);
 230         else
 231                 B_DSET(GET_BKEYDATA(h, indx)->type);
 232         (void)__bam_ca_delete(dbp, pgno, indx, NULL);
 233
 234         ret = memp_fput(dbp->mpf, h, DB_MPOOL_DIRTY);
 235
 236 err:    PUTHANDLE(dbp);
 237         return (ret);
 238 }
 239
 240 /*
 241  * __bam_get --
 242  *      Retrieve a key/data pair from the tree.
 243  *
 244  * PUBLIC: int __bam_get __P((DB *, DB_TXN *, DBT *, DBT *, int));
 245  */
 246 int
 247 __bam_get(argdbp, txn, key, data, flags)
 248         DB *argdbp;
 249         DB_TXN *txn;
 250         DBT *key, *data;
 251         int flags;
 252 {
 253         DBC dbc;
 254         CURSOR cp;
 255         int ret;
 256
 257         DEBUG_LREAD(argdbp, txn, "bam_get", key, NULL, flags);
 258
 259         /* Check for invalid flags. */
 260         if ((ret = __db_getchk(argdbp, key, data, flags)) != 0)
 261                 return (ret);
 262
 263         /* Build an internal cursor. */
 264         memset(&cp, 0, sizeof(cp));
 265         cp.dbc = &dbc;
 266         cp.pgno = cp.dpgno = PGNO_INVALID;
 267         cp.lock = LOCK_INVALID;
 268         cp.flags = C_INTERNAL;
 269
 270         /* Build an external cursor. */
 271         memset(&dbc, 0, sizeof(dbc));
 272         dbc.dbp = argdbp;
 273         dbc.txn = txn;
 274         dbc.internal = &cp;
 275
 276         /* Get the key. */
 277         return(__bam_c_get(&dbc,
 278             key, data, LF_ISSET(DB_SET_RECNO) ? DB_SET_RECNO : DB_SET));
 279 }
 280
 281 /*
 282  * __bam_c_get --
 283  *      Get using a cursor (btree).
 284  */
 285 static int
 286 __bam_c_get(dbc, key, data, flags)
 287         DBC *dbc;
 288         DBT *key, *data;
 289         int flags;
 290 {
 291         BTREE *t;
 292         CURSOR *cp, copy;
 293         DB *dbp;
 294         PAGE *h;
 295         int exact, ret;
 296
 297         DEBUG_LREAD(dbc->dbp, dbc->txn, "bam_c_get",
 298             flags == DB_SET || flags == DB_SET_RANGE ? key : NULL, NULL, flags);
 299
 300         cp = dbc->internal;
 301
 302         /* Check for invalid flags. */
 303         if ((ret = __db_cgetchk(dbc->dbp,
 304             key, data, flags, cp->pgno != PGNO_INVALID)) != 0)
 305                 return (ret);
 306
 307         GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
 308         t = dbp->internal;
 309
 310         /*
 311          * Break out the code to return a cursor's record number.  It
 312          * has nothing to do with the cursor get code except that it's
 313          * been rammed into the interface.
 314          */
 315         if (LF_ISSET(DB_GET_RECNO)) {
 316                 ret = __bam_c_rget(dbp, cp, key, data, flags);
 317                 PUTHANDLE(dbp);
 318                 return (ret);
 319         }
 320
 321         /* Initialize the cursor for a new retrieval. */
 322         copy = *cp;
 323         cp->page = NULL;
 324         cp->lock = LOCK_INVALID;
 325
 326         switch (flags) {
 327         case DB_CURRENT:
 328                 /* It's not possible to return a deleted record. */
 329                 if (F_ISSET(cp, C_DELETED | C_REPLACE)) {
 330                         PUTHANDLE(dbp);
 331                         return (DB_KEYEMPTY);
 332                 }
 333
 334                 /* Get the page with the current item on it. */
 335                 if ((ret = __bam_pget(dbp, &cp->page, &cp->pgno, 0)) != 0)
 336                         goto err;
 337                 break;
 338         case DB_NEXT:
 339                 if (cp->pgno != PGNO_INVALID) {
 340                         if ((ret = __bam_c_next(dbp, cp, 1)) != 0)
 341                                 goto err;
 342                         break;
 343                 }
 344                 /* FALLTHROUGH */
 345         case DB_FIRST:
 346                 if ((ret = __bam_c_first(dbp, cp)) != 0)
 347                         goto err;
 348                 break;
 349         case DB_PREV:
 350                 if (cp->pgno != PGNO_INVALID) {
 351                         if ((ret = __bam_c_prev(dbp, cp)) != 0)
 352                                 goto err;
 353                         break;
 354                 }
 355                 /* FALLTHROUGH */
 356         case DB_LAST:
 357                 if ((ret = __bam_c_last(dbp, cp)) != 0)
 358                         goto err;
 359                 break;
 360         case DB_SET_RECNO:
 361                 exact = 1;
 362                 if ((ret =
 363                     __bam_c_search(dbp, cp, key, S_FIND, 1, &exact)) != 0)
 364                         goto err;
 365                 break;
 366         case DB_SET:
 367                 exact = 1;
 368                 if ((ret =
 369                     __bam_c_search(dbp, cp, key, S_FIND, 0, &exact)) != 0)
 370                         goto err;
 371                 break;
 372         case DB_SET_RANGE:
 373                 exact = 0;
 374                 if ((ret =
 375                     __bam_c_search(dbp, cp, key, S_FIND, 0, &exact)) != 0)
 376                         goto err;
 377                 break;
 378         }
 379
 380         /*
 381          * Return the key if the user didn't give us one.  If we've moved to
 382          * a duplicate page, we may no longer have a pointer to the main page,
 383          * so we have to go get it.  We know that it's already read-locked,
 384          * however, so we don't have to acquire a new lock.
 385          */
 386         if (flags != DB_SET) {
 387                 if (cp->dpgno != PGNO_INVALID) {
 388                         if ((ret = __bam_pget(dbp, &h, &cp->pgno, 0)) != 0)
 389                                 goto err;
 390                 } else
 391                         h = cp->page;
 392                 ret = __db_ret(dbp,
 393                     h, cp->indx, key, &t->bt_rkey.data, &t->bt_rkey.ulen);
 394                 if (cp->dpgno != PGNO_INVALID)
 395                         (void)memp_fput(dbp->mpf, h, 0);
 396                 if (ret)
 397                         goto err;
 398         }
 399
 400         /* Return the data. */
 401         if ((ret = __db_ret(dbp, cp->page,
 402             cp->dpgno == PGNO_INVALID ? cp->indx + O_INDX : cp->dindx,
 403             data, &t->bt_rdata.data, &t->bt_rdata.ulen)) != 0)
 404                 goto err;
 405
 406         /*
 407          * If the previous cursor record has been deleted, delete it.  The
 408          * returned key isn't a deleted key, so clear the flag.
 409          */
 410         if (F_ISSET(&copy, C_DELETED) && __bam_c_physdel(dbp, &copy, cp->page))
 411                 goto err;
 412         F_CLR(cp, C_DELETED | C_REPLACE);
 413
 414         /* Release the previous lock, if any. */
 415         if (copy.lock != LOCK_INVALID)
 416                 (void)__BT_TLPUT(dbp, copy.lock);
 417
 418         /* Release the pinned page. */
 419         ret = memp_fput(dbp->mpf, cp->page, 0);
 420
 421         /* Internal cursors don't hold locks. */
 422         if (F_ISSET(cp, C_INTERNAL) && cp->lock != LOCK_INVALID)
 423                 (void)__BT_TLPUT(dbp, cp->lock);
 424
 425         ++t->lstat.bt_get;
 426
 427         if (0) {
 428 err:            if (cp->page != NULL)
 429                         (void)memp_fput(dbp->mpf, cp->page, 0);
 430                 if (cp->lock != LOCK_INVALID)
 431                         (void)__BT_TLPUT(dbp, cp->lock);
 432                 *cp = copy;
 433         }
 434
 435         PUTHANDLE(dbp);
 436         return (ret);
 437 }
 438
 439 /*
 440  * __bam_c_rget --
 441  *      Return the record number for a cursor.
 442  */
 443 static int
 444 __bam_c_rget(dbp, cp, key, data, flags)
 445         DB *dbp;
 446         CURSOR *cp;
 447         DBT *key, *data;
 448         int flags;
 449 {
 450         BTREE *t;
 451         DBT dbt;
 452         db_recno_t recno;
 453         int exact, ret;
 454
 455         /* Get the page with the current item on it. */
 456         if ((ret = __bam_pget(dbp, &cp->page, &cp->pgno, 0)) != 0)
 457                 return (ret);
 458
 459         /* Get a copy of the key. */
 460         memset(&dbt, 0, sizeof(DBT));
 461         dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
 462         if ((ret = __db_ret(dbp, cp->page, cp->indx, &dbt, NULL, NULL)) != 0)
 463                 goto err;
 464
 465         exact = 1;
 466         if ((ret = __bam_search(dbp, &dbt, S_FIND, 1, &recno, &exact)) != 0)
 467                 goto err;
 468
 469         t = dbp->internal;
 470         ret = __db_retcopy(data, &recno, sizeof(recno),
 471             &t->bt_rdata.data, &t->bt_rdata.ulen, dbp->db_malloc);
 472
 473         /* Release the stack. */
 474         __bam_stkrel(dbp);
 475
 476 err:    (void)memp_fput(dbp->mpf, cp->page, 0);
 477         free(dbt.data);
 478         return (ret);
 479 }
 480
 481 /*
 482  * __bam_c_put --
 483  *      Put using a cursor.
 484  */
 485 static int
 486 __bam_c_put(dbc, key, data, flags)
 487         DBC *dbc;
 488         DBT *key, *data;
 489         int flags;
 490 {
 491         BTREE *t;
 492         CURSOR *cp, copy;
 493         DB *dbp;
 494         DBT dbt;
 495         db_indx_t indx;
 496         db_pgno_t pgno;
 497         int exact, needkey, ret;
 498         void *arg;
 499
 500         DEBUG_LWRITE(dbc->dbp, dbc->txn, "bam_c_put",
 501             flags == DB_KEYFIRST || flags == DB_KEYLAST ? key : NULL,
 502             data, flags);
 503
 504         cp = dbc->internal;
 505
 506         if ((ret = __db_cputchk(dbc->dbp, key, data, flags,
 507             F_ISSET(dbc->dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
 508                 return (ret);
 509
 510         GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
 511         t = dbp->internal;
 512
 513         /* Initialize the cursor for a new retrieval. */
 514         copy = *cp;
 515         cp->page = NULL;
 516         cp->lock = LOCK_INVALID;
 517
 518         /*
 519          * To split, we need a valid key for the page.  Since it's a cursor,
 520          * we have to build one.
 521          */
 522         if (0) {
 523 split:          if (needkey) {
 524                         memset(&dbt, 0, sizeof(DBT));
 525                         ret = __db_ret(dbp, cp->page, indx,
 526                             &dbt, &t->bt_rkey.data, &t->bt_rkey.ulen);
 527
 528                         DISCARD(dbp, cp);
 529
 530                         if (ret)
 531                                 goto err;
 532                         arg = &dbt;
 533                 } else {
 534                         (void)__bam_stkrel(dbp);
 535                         arg = key;
 536                 }
 537                 if ((ret = __bam_split(dbp, arg)) != 0)
 538                         goto err;
 539         }
 540
 541         /* If there's no key supplied, use the cursor. */
 542         if (flags == DB_KEYFIRST || flags == DB_KEYLAST)
 543                 needkey = 0;
 544         else {
 545                 needkey = 1;
 546                 if (cp->dpgno == PGNO_INVALID) {
 547                         pgno = cp->pgno;
 548                         indx = cp->indx;
 549                 } else {
 550                         pgno = cp->dpgno;
 551                         indx = cp->dindx;
 552                 }
 553                 /* Acquire the current page. */
 554                 if ((ret = __bam_lget(dbp,
 555                     0, cp->pgno, DB_LOCK_WRITE, &cp->lock)) != 0)
 556                         goto err;
 557                 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
 558                         goto err;
 559         }
 560
 561         ret = 0;
 562         switch (flags) {
 563         case DB_AFTER:
 564         case DB_BEFORE:
 565         case DB_CURRENT:
 566                 if ((ret = __bam_iitem(dbp, &cp->page,
 567                     &indx, key, data, flags, 0)) == DB_NEEDSPLIT)
 568                         goto split;
 569                 break;
 570         case DB_KEYFIRST:
 571                 exact = 0;
 572                 if ((ret =
 573                     __bam_c_search(dbp, cp, key, S_KEYFIRST, 0, &exact)) != 0)
 574                         goto err;
 575
 576                 indx = cp->dpgno == PGNO_INVALID ? cp->indx : cp->dindx;
 577                 if ((ret = __bam_iitem(dbp, &cp->page, &indx, key,
 578                     data, DB_BEFORE, exact ? 0 : BI_NEWKEY)) == DB_NEEDSPLIT)
 579                         goto split;
 580                 if (ret)
 581                         goto err;
 582                 break;
 583         case DB_KEYLAST:
 584                 exact = 0;
 585                 if ((ret =
 586                     __bam_c_search(dbp, cp, key, S_KEYLAST, 0, &exact)) != 0)
 587                         goto err;
 588
 589                 indx = cp->dpgno == PGNO_INVALID ? cp->indx : cp->dindx;
 590                 if ((ret = __bam_iitem(dbp, &cp->page, &indx, key,
 591                     data, DB_AFTER, exact ? 0 : BI_NEWKEY)) == DB_NEEDSPLIT)
 592                         goto split;
 593                 break;
 594         }
 595         if (ret)
 596                 goto err;
 597
 598         /*
 599          * Update the cursor to point to the new entry.  The new entry was
 600          * stored on the current page, because we split pages until it was
 601          * possible.
 602          */
 603         if (cp->dpgno == PGNO_INVALID)
 604                 cp->indx = indx;
 605         else
 606                 cp->dindx = indx;
 607
 608         /*
 609          * If the previous cursor record has been deleted, delete it.  The
 610          * returned key isn't a deleted key, so clear the flag.
 611          */
 612         if (F_ISSET(&copy, C_DELETED) &&
 613             (ret = __bam_c_physdel(dbp, &copy, cp->page)) != 0)
 614                 goto err;
 615         F_CLR(cp, C_DELETED | C_REPLACE);
 616
 617         /* Release the previous lock, if any. */
 618         if (copy.lock != LOCK_INVALID)
 619                 (void)__BT_TLPUT(dbp, copy.lock);
 620
 621         /* Discard the pinned page. */
 622         ret = memp_fput(dbp->mpf, cp->page, 0);
 623         if (0) {
 624 err:            if (cp->page != NULL)
 625                         (void)memp_fput(dbp->mpf, cp->page, 0);
 626                 if (cp->lock != LOCK_INVALID)
 627                         (void)__BT_TLPUT(dbp, cp->lock);
 628                 *cp = copy;
 629         }
 630
 631         PUTHANDLE(dbp);
 632         return (ret);
 633 }
 634
 635 /*
 636  * __bam_c_first --
 637  *      Return the first record.
 638  */
 639 static int
 640 __bam_c_first(dbp, cp)
 641         DB *dbp;
 642         CURSOR *cp;
 643 {
 644         db_pgno_t pgno;
 645         int ret;
 646
 647         /* Walk down the left-hand side of the tree. */
 648         for (pgno = PGNO_ROOT;;) {
 649                 if ((ret =
 650                     __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
 651                         return (ret);
 652                 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
 653                         return (ret);
 654
 655                 /* If we find a leaf page, we're done. */
 656                 if (ISLEAF(cp->page))
 657                         break;
 658
 659                 pgno = GET_BINTERNAL(cp->page, 0)->pgno;
 660                 DISCARD(dbp, cp);
 661         }
 662
 663         cp->pgno = cp->page->pgno;
 664         cp->indx = 0;
 665         cp->dpgno = PGNO_INVALID;
 666
 667         /* If it's an empty page or a deleted record, go to the next one. */
 668         if (NUM_ENT(cp->page) == 0 ||
 669             B_DISSET(GET_BKEYDATA(cp->page, cp->indx + O_INDX)->type))
 670                 if ((ret = __bam_c_next(dbp, cp, 0)) != 0)
 671                         return (ret);
 672
 673         /* If it's a duplicate reference, go to the first entry. */
 674         if ((ret = __bam_ovfl_chk(dbp, cp, O_INDX, 0)) != 0)
 675                 return (ret);
 676
 677         /* If it's a deleted record, go to the next one. */
 678         if (cp->dpgno != PGNO_INVALID &&
 679             B_DISSET(GET_BKEYDATA(cp->page, cp->dindx)->type))
 680                 if ((ret = __bam_c_next(dbp, cp, 0)) != 0)
 681                         return (ret);
 682         return (0);
 683 }
 684
 685 /*
 686  * __bam_c_last --
 687  *      Return the last record.
 688  */
 689 static int
 690 __bam_c_last(dbp, cp)
 691         DB *dbp;
 692         CURSOR *cp;
 693 {
 694         db_pgno_t pgno;
 695         int ret;
 696
 697         /* Walk down the right-hand side of the tree. */
 698         for (pgno = PGNO_ROOT;;) {
 699                 if ((ret =
 700                     __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
 701                         return (ret);
 702                 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
 703                         return (ret);
 704
 705                 /* If we find a leaf page, we're done. */
 706                 if (ISLEAF(cp->page))
 707                         break;
 708
 709                 pgno =
 710                     GET_BINTERNAL(cp->page, NUM_ENT(cp->page) - O_INDX)->pgno;
 711                 DISCARD(dbp, cp);
 712         }
 713
 714         cp->pgno = cp->page->pgno;
 715         cp->indx = NUM_ENT(cp->page) == 0 ? 0 : NUM_ENT(cp->page) - P_INDX;
 716         cp->dpgno = PGNO_INVALID;
 717
 718         /* If it's an empty page or a deleted record, go to the previous one. */
 719         if (NUM_ENT(cp->page) == 0 ||
 720             B_DISSET(GET_BKEYDATA(cp->page, cp->indx + O_INDX)->type))
 721                 if ((ret = __bam_c_prev(dbp, cp)) != 0)
 722                         return (ret);
 723
 724         /* If it's a duplicate reference, go to the last entry. */
 725         if ((ret = __bam_ovfl_chk(dbp, cp, cp->indx + O_INDX, 1)) != 0)
 726                 return (ret);
 727
 728         /* If it's a deleted record, go to the previous one. */
 729         if (cp->dpgno != PGNO_INVALID &&
 730             B_DISSET(GET_BKEYDATA(cp->page, cp->dindx)->type))
 731                 if ((ret = __bam_c_prev(dbp, cp)) != 0)
 732                         return (ret);
 733         return (0);
 734 }
 735
 736 /*
 737  * __bam_c_next --
 738  *      Move to the next record.
 739  */
 740 static int
 741 __bam_c_next(dbp, cp, initial_move)
 742         DB *dbp;
 743         CURSOR *cp;
 744         int initial_move;
 745 {
 746         db_indx_t adjust, indx;
 747         db_pgno_t pgno;
 748         int ret;
 749
 750         /*
 751          * We're either moving through a page of duplicates or a btree leaf
 752          * page.
 753          */
 754         if (cp->dpgno == PGNO_INVALID) {
 755                 adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
 756                 pgno = cp->pgno;
 757                 indx = cp->indx;
 758         } else {
 759                 adjust = O_INDX;
 760                 pgno = cp->dpgno;
 761                 indx = cp->dindx;
 762         }
 763         if (cp->page == NULL) {
 764                 if ((ret =
 765                     __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
 766                         return (ret);
 767                 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
 768                         return (ret);
 769         }
 770
 771         /*
 772          * If at the end of the page, move to a subsequent page.
 773          *
 774          * !!!
 775          * Check for >= NUM_ENT.  If we're here as the result of a search that
 776          * landed us on NUM_ENT, we'll increment indx before we test.
 777          *
 778          * !!!
 779          * This code handles empty pages and pages with only deleted entries.
 780          */
 781         if (initial_move)
 782                 indx += adjust;
 783         for (;;) {
 784                 if (indx >= NUM_ENT(cp->page)) {
 785                         pgno = cp->page->next_pgno;
 786                         DISCARD(dbp, cp);
 787
 788                         /*
 789                          * If we're in a btree leaf page, we've reached the end
 790                          * of the tree.  If we've reached the end of a page of
 791                          * duplicates, continue from the btree leaf page where
 792                          * we found this page of duplicates.
 793                          */
 794                         if (pgno == PGNO_INVALID) {
 795                                 /* If in a btree leaf page, it's EOF. */
 796                                 if (cp->dpgno == PGNO_INVALID)
 797                                         return (DB_NOTFOUND);
 798
 799                                 /* Continue from the last btree leaf page. */
 800                                 cp->dpgno = PGNO_INVALID;
 801
 802                                 adjust = P_INDX;
 803                                 pgno = cp->pgno;
 804                                 indx = cp->indx + P_INDX;
 805                         } else
 806                                 indx = 0;
 807
 808                         if ((ret = __bam_lget(dbp,
 809                             0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
 810                                 return (ret);
 811                         if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
 812                                 return (ret);
 813                         continue;
 814                 }
 815
 816                 /* Ignore deleted records. */
 817                 if (dbp->type == DB_BTREE &&
 818                     ((cp->dpgno == PGNO_INVALID &&
 819                     B_DISSET(GET_BKEYDATA(cp->page, indx + O_INDX)->type)) ||
 820                     (cp->dpgno != PGNO_INVALID &&
 821                     B_DISSET(GET_BKEYDATA(cp->page, indx)->type)))) {
 822                         indx += adjust;
 823                         continue;
 824                 }
 825
 826                 /*
 827                  * If we're not in a duplicates page, check to see if we've
 828                  * found a page of duplicates, in which case we move to the
 829                  * first entry.
 830                  */
 831                 if (cp->dpgno == PGNO_INVALID) {
 832                         cp->pgno = cp->page->pgno;
 833                         cp->indx = indx;
 834
 835                         if ((ret =
 836                             __bam_ovfl_chk(dbp, cp, indx + O_INDX, 0)) != 0)
 837                                 return (ret);
 838                         if (cp->dpgno != PGNO_INVALID) {
 839                                 indx = cp->dindx;
 840                                 adjust = O_INDX;
 841                                 continue;
 842                         }
 843                 } else {
 844                         cp->dpgno = cp->page->pgno;
 845                         cp->dindx = indx;
 846                 }
 847                 break;
 848         }
 849         return (0);
 850 }
 851
 852 /*
 853  * __bam_c_prev --
 854  *      Move to the previous record.
 855  */
 856 static int
 857 __bam_c_prev(dbp, cp)
 858         DB *dbp;
 859         CURSOR *cp;
 860 {
 861         db_indx_t indx, adjust;
 862         db_pgno_t pgno;
 863         int ret, set_indx;
 864
 865         /*
 866          * We're either moving through a page of duplicates or a btree leaf
 867          * page.
 868          */
 869         if (cp->dpgno == PGNO_INVALID) {
 870                 adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
 871                 pgno = cp->pgno;
 872                 indx = cp->indx;
 873         } else {
 874                 adjust = O_INDX;
 875                 pgno = cp->dpgno;
 876                 indx = cp->dindx;
 877         }
 878         if (cp->page == NULL) {
 879                 if ((ret =
 880                     __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
 881                         return (ret);
 882                 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
 883                         return (ret);
 884         }
 885
 886         /*
 887          * If at the beginning of the page, move to any previous one.
 888          *
 889          * !!!
 890          * This code handles empty pages and pages with only deleted entries.
 891          */
 892         for (;;) {
 893                 if (indx == 0) {
 894                         pgno = cp->page->prev_pgno;
 895                         DISCARD(dbp, cp);
 896
 897                         /*
 898                          * If we're in a btree leaf page, we've reached the
 899                          * beginning of the tree.  If we've reached the first
 900                          * of a page of duplicates, continue from the btree
 901                          * leaf page where we found this page of duplicates.
 902                          */
 903                         if (pgno == PGNO_INVALID) {
 904                                 /* If in a btree leaf page, it's SOF. */
 905                                 if (cp->dpgno == PGNO_INVALID)
 906                                         return (DB_NOTFOUND);
 907
 908                                 /* Continue from the last btree leaf page. */
 909                                 cp->dpgno = PGNO_INVALID;
 910
 911                                 adjust = P_INDX;
 912                                 pgno = cp->pgno;
 913                                 indx = cp->indx;
 914                                 set_indx = 0;
 915                         } else
 916                                 set_indx = 1;
 917
 918                         if ((ret = __bam_lget(dbp,
 919                             0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
 920                                 return (ret);
 921                         if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
 922                                 return (ret);
 923
 924                         if (set_indx)
 925                                 indx = NUM_ENT(cp->page);
 926                         if (indx == 0)
 927                                 continue;
 928                 }
 929
 930                 /* Ignore deleted records. */
 931                 indx -= adjust;
 932                 if (dbp->type == DB_BTREE &&
 933                     ((cp->dpgno == PGNO_INVALID &&
 934                     B_DISSET(GET_BKEYDATA(cp->page, indx + O_INDX)->type)) ||
 935                     (cp->dpgno != PGNO_INVALID &&
 936                     B_DISSET(GET_BKEYDATA(cp->page, indx)->type))))
 937                         continue;
 938
 939                 /*
 940                  * If we're not in a duplicates page, check to see if we've
 941                  * found a page of duplicates, in which case we move to the
 942                  * last entry.
 943                  */
 944                 if (cp->dpgno == PGNO_INVALID) {
 945                         cp->pgno = cp->page->pgno;
 946                         cp->indx = indx;
 947
 948                         if ((ret =
 949                             __bam_ovfl_chk(dbp, cp, indx + O_INDX, 1)) != 0)
 950                                 return (ret);
 951                         if (cp->dpgno != PGNO_INVALID) {
 952                                 indx = cp->dindx + O_INDX;
 953                                 adjust = O_INDX;
 954                                 continue;
 955                         }
 956                 } else {
 957                         cp->dpgno = cp->page->pgno;
 958                         cp->dindx = indx;
 959                 }
 960                 break;
 961         }
 962         return (0);
 963 }
 964
 965 /*
 966  * __bam_c_search --
 967  *      Move to a specified record.
 968  */
 969 static int
 970 __bam_c_search(dbp, cp, key, flags, isrecno, exactp)
 971         DB *dbp;
 972         CURSOR *cp;
 973         const DBT *key;
 974         u_int flags;
 975         int isrecno, *exactp;
 976 {
 977         BTREE *t;
 978         db_recno_t recno;
 979         int needexact, ret;
 980
 981         t = dbp->internal;
 982         needexact = *exactp;
 983
 984         /*
 985          * Find any matching record; the search function pins the page.  Make
 986          * sure it's a valid key (__bam_search may return an index just past
 987          * the end of a page) and return it.
 988          */
 989         if (isrecno) {
 990                 if ((ret = __ram_getno(dbp, key, &recno, 0)) != 0)
 991                         return (ret);
 992                 ret = __bam_rsearch(dbp, &recno, flags, 1, exactp);
 993         } else
 994                 ret = __bam_search(dbp, key, flags, 1, NULL, exactp);
 995         if (ret != 0)
 996                 return (ret);
 997
 998         cp->page = t->bt_csp->page;
 999         cp->pgno = cp->page->pgno;
1000         cp->indx = t->bt_csp->indx;
1001         cp->lock = t->bt_csp->lock;
1002         cp->dpgno = PGNO_INVALID;
1003
1004         /*
1005          * If we have an exact match, make sure that we're not looking at a
1006          * chain of duplicates -- if so, move to an entry in that chain.
1007          */
1008         if (*exactp) {
1009                 if ((ret = __bam_ovfl_chk(dbp,
1010                     cp, cp->indx + O_INDX, LF_ISSET(S_DUPLAST))) != 0)
1011                         return (ret);
1012         } else
1013                 if (needexact)
1014                         return (DB_NOTFOUND);
1015
1016         /* If past the end of a page, find the next entry. */
1017         if (cp->indx == NUM_ENT(cp->page) &&
1018             (ret = __bam_c_next(dbp, cp, 0)) != 0)
1019                 return (ret);
1020
1021         /* If it's a deleted record, go to the next or previous one. */
1022         if (cp->dpgno != PGNO_INVALID &&
1023             B_DISSET(GET_BKEYDATA(cp->page, cp->dindx)->type))
1024                 if (flags == S_KEYLAST) {
1025                         if ((ret = __bam_c_prev(dbp, cp)) != 0)
1026                                 return (ret);
1027                 } else
1028                         if ((ret = __bam_c_next(dbp, cp, 0)) != 0)
1029                                 return (ret);
1030         return (0);
1031 }
1032
1033 /*
1034  * __bam_ovfl_chk --
1035  *      Check for an overflow record, and if found, move to the correct
1036  *      record.
1037  *
1038  * PUBLIC: int __bam_ovfl_chk __P((DB *, CURSOR *, u_int32_t, int));
1039  */
1040 int
1041 __bam_ovfl_chk(dbp, cp, indx, to_end)
1042         DB *dbp;
1043         CURSOR *cp;
1044         u_int32_t indx;
1045         int to_end;
1046 {
1047         BOVERFLOW *bo;
1048         db_pgno_t pgno;
1049         int ret;
1050
1051         /* Check for an overflow entry. */
1052         bo = GET_BOVERFLOW(cp->page, indx);
1053         if (B_TYPE(bo->type) != B_DUPLICATE)
1054                 return (0);
1055
1056         /*
1057          * If we find one, go to the duplicates page, and optionally move
1058          * to the last record on that page.
1059          *
1060          * XXX
1061          * We don't lock duplicates pages, we've already got the correct
1062          * lock on the main page.
1063          */
1064         pgno = bo->pgno;
1065         if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
1066                 return (ret);
1067         cp->page = NULL;
1068         if (to_end) {
1069                 if ((ret = __db_dend(dbp, pgno, &cp->page)) != 0)
1070                         return (ret);
1071                 indx = NUM_ENT(cp->page) - O_INDX;
1072         } else {
1073                 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
1074                         return (ret);
1075                 indx = 0;
1076         }
1077
1078         /* Update the duplicate entry in the cursor. */
1079         cp->dpgno = cp->page->pgno;
1080         cp->dindx = indx;
1081
1082         return (0);
1083 }
1084
1085 #ifdef DEBUG
1086 /*
1087  * __bam_cprint --
1088  *      Display the current btree cursor list.
1089  */
1090 int
1091 __bam_cprint(dbp)
1092         DB *dbp;
1093 {
1094         CURSOR *cp;
1095         DBC *dbc;
1096
1097         DB_THREAD_LOCK(dbp);
1098         for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1099             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1100                 cp = (CURSOR *)dbc->internal;
1101                 fprintf(stderr,
1102                     "%#0x: page: %lu index: %lu dpage %lu dindex: %lu",
1103                     (u_int)cp, (u_long)cp->pgno, (u_long)cp->indx,
1104                     (u_long)cp->dpgno, (u_long)cp->dindx);
1105                 if (F_ISSET(cp, C_DELETED))
1106                         fprintf(stderr, "(deleted)");
1107                 fprintf(stderr, "\n");
1108         }
1109         DB_THREAD_UNLOCK(dbp);
1110         return (0);
1111 }
1112 #endif /* DEBUG */
1113
1114 /*
1115  * __bam_ca_delete --
1116  *      Check if any of the cursors refer to the item we are about to delete.
1117  *      We'll return the number of cursors that refer to the item in question.
1118  *      If a cursor does refer to the item, then we set its deleted bit.
1119  *
1120  * PUBLIC: int __bam_ca_delete __P((DB *, db_pgno_t, u_int32_t, CURSOR *));
1121  */
1122 int
1123 __bam_ca_delete(dbp, pgno, indx, curs)
1124         DB *dbp;
1125         db_pgno_t pgno;
1126         u_int32_t indx;
1127         CURSOR *curs;
1128 {
1129         DBC *dbc;
1130         CURSOR *cp;
1131         int count;
1132
1133         /*
1134          * Adjust the cursors.  We don't have to review the cursors for any
1135          * process other than the current one, because we have the page write
1136          * locked at this point, and any other process had better be using a
1137          * different locker ID, meaning that only cursors in our process can
1138          * be on the page.
1139          *
1140          * It's possible for multiple cursors within the thread to have write
1141          * locks on the same page, but, cursors within a thread must be single
1142          * threaded, so all we're locking here is the cursor linked list.
1143          *
1144          * indx refers to the first of what might be a duplicate set.  The
1145          * cursor passed in is the one initiating the delete, so we don't
1146          * want to count it.
1147          */
1148         DB_THREAD_LOCK(dbp);
1149         for (count = 0, dbc = TAILQ_FIRST(&dbp->curs_queue);
1150             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1151                 cp = (CURSOR *)dbc->internal;
1152                 if ((curs != cp &&
1153                     cp->pgno == pgno && cp->indx == indx) ||
1154                     (cp->dpgno == pgno && cp->dindx == indx)) {
1155                         ++count;
1156                         F_SET(cp, C_DELETED);
1157                 }
1158         }
1159         DB_THREAD_UNLOCK(dbp);
1160         return (count);
1161 }
1162
1163 /*
1164  * __bam_ca_di --
1165  *      Adjust the cursors during a delete or insert.
1166  *
1167  * PUBLIC: void __bam_ca_di __P((DB *, db_pgno_t, u_int32_t, int));
1168  */
1169 void
1170 __bam_ca_di(dbp, pgno, indx, value)
1171         DB *dbp;
1172         db_pgno_t pgno;
1173         u_int32_t indx;
1174         int value;
1175 {
1176         CURSOR *cp;
1177         DBC *dbc;
1178
1179         /* Recno is responsible for its own adjustments. */
1180         if (dbp->type == DB_RECNO)
1181                 return;
1182
1183         /*
1184          * Adjust the cursors.  See the comment in __bam_ca_delete().
1185          */
1186         DB_THREAD_LOCK(dbp);
1187         for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1188             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1189                 cp = (CURSOR *)dbc->internal;
1190                 if (cp->pgno == pgno && cp->indx >= indx)
1191                         cp->indx += value;
1192                 if (cp->dpgno == pgno && cp->dindx >= indx)
1193                         cp->dindx += value;
1194         }
1195         DB_THREAD_UNLOCK(dbp);
1196 }
1197
1198 /*
1199  * __bam_ca_dup --
1200  *      Adjust the cursors when moving data items to a duplicates page.
1201  *
1202  * PUBLIC: void __bam_ca_dup __P((DB *,
1203  * PUBLIC:    db_pgno_t, u_int32_t, u_int32_t, db_pgno_t, u_int32_t));
1204  */
1205 void
1206 __bam_ca_dup(dbp, fpgno, first, fi, tpgno, ti)
1207         DB *dbp;
1208         db_pgno_t fpgno, tpgno;
1209         u_int32_t first, fi, ti;
1210 {
1211         CURSOR *cp;
1212         DBC *dbc;
1213
1214         /*
1215          * Adjust the cursors.  See the comment in __bam_ca_delete().
1216          *
1217          * No need to test duplicates, this only gets called when moving
1218          * leaf page data items onto a duplicates page.
1219          */
1220         DB_THREAD_LOCK(dbp);
1221         for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1222             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1223                 cp = (CURSOR *)dbc->internal;
1224                 /*
1225                  * Ignore matching entries that have already been moved,
1226                  * we move from the same location on the leaf page more
1227                  * than once.
1228                  */
1229                 if (cp->dpgno == PGNO_INVALID &&
1230                     cp->pgno == fpgno && cp->indx == fi) {
1231                         cp->indx = first;
1232                         cp->dpgno = tpgno;
1233                         cp->dindx = ti;
1234                 }
1235         }
1236         DB_THREAD_UNLOCK(dbp);
1237 }
1238
1239 /*
1240  * __bam_ca_move --
1241  *      Adjust the cursors when moving data items to another page.
1242  *
1243  * PUBLIC: void __bam_ca_move __P((DB *, BTREE *, db_pgno_t, db_pgno_t));
1244  */
1245 void
1246 __bam_ca_move(dbp, t, fpgno, tpgno)
1247         DB *dbp;
1248         BTREE *t;
1249         db_pgno_t fpgno, tpgno;
1250 {
1251         CURSOR *cp;
1252         DBC *dbc;
1253
1254         /* Recno is responsible for its own adjustments. */
1255         if (dbp->type == DB_RECNO)
1256                 return;
1257
1258         /*
1259          * Adjust the cursors.  See the comment in __bam_ca_delete().
1260          *
1261          * No need to test duplicates, this only gets called when copying
1262          * over the root page with a leaf or internal page.
1263          */
1264         DB_THREAD_LOCK(dbp);
1265         for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1266             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1267                 cp = (CURSOR *)dbc->internal;
1268                 if (cp->pgno == fpgno)
1269                         cp->pgno = tpgno;
1270         }
1271         DB_THREAD_UNLOCK(dbp);
1272 }
1273
1274 /*
1275  * __bam_ca_replace --
1276  *      Check if any of the cursors refer to the item we are about to replace.
1277  *      If so, their flags should be changed from deleted to replaced.
1278  *
1279  * PUBLIC: void __bam_ca_replace
1280  * PUBLIC:    __P((DB *, db_pgno_t, u_int32_t, ca_replace_arg));
1281  */
1282 void
1283 __bam_ca_replace(dbp, pgno, indx, pass)
1284         DB *dbp;
1285         db_pgno_t pgno;
1286         u_int32_t indx;
1287         ca_replace_arg pass;
1288 {
1289         CURSOR *cp;
1290         DBC *dbc;
1291
1292         /*
1293          * Adjust the cursors.  See the comment in __bam_ca_delete().
1294          *
1295          * Find any cursors that have logically deleted a record we're about
1296          * to overwrite.
1297          *
1298          * Pass == REPLACE_SETUP:
1299          *      Set C_REPLACE_SETUP so we can find the cursors again.
1300          *
1301          * Pass == REPLACE_SUCCESS:
1302          *      Clear C_DELETED and C_REPLACE_SETUP, set C_REPLACE, the
1303          *      overwrite was successful.
1304          *
1305          * Pass == REPLACE_FAILED:
1306          *      Clear C_REPLACE_SETUP, the overwrite failed.
1307          *
1308          * For REPLACE_SUCCESS and REPLACE_FAILED, we reset the indx value
1309          * for the cursor as it may have been changed by other cursor update
1310          * routines as the item was deleted/inserted.
1311          */
1312         DB_THREAD_LOCK(dbp);
1313         switch (pass) {
1314         case REPLACE_SETUP:                     /* Setup. */
1315                 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1316                     dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1317                         cp = (CURSOR *)dbc->internal;
1318                         if ((cp->pgno == pgno && cp->indx == indx) ||
1319                             (cp->dpgno == pgno && cp->dindx == indx))
1320                                 F_SET(cp, C_REPLACE_SETUP);
1321                 }
1322                 break;
1323         case REPLACE_SUCCESS:                   /* Overwrite succeeded. */
1324                 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1325                     dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1326                         cp = (CURSOR *)dbc->internal;
1327                         if (F_ISSET(cp, C_REPLACE_SETUP)) {
1328                                 if (cp->dpgno == pgno)
1329                                         cp->dindx = indx;
1330                                 if (cp->pgno == pgno)
1331                                         cp->indx = indx;
1332                                 F_SET(cp, C_REPLACE);
1333                                 F_CLR(cp, C_DELETED | C_REPLACE_SETUP);
1334                         }
1335                 }
1336                 break;
1337         case REPLACE_FAILED:                    /* Overwrite failed. */
1338                 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1339                     dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1340                         cp = (CURSOR *)dbc->internal;
1341                         if (F_ISSET(cp, C_REPLACE_SETUP)) {
1342                                 if (cp->dpgno == pgno)
1343                                         cp->dindx = indx;
1344                                 if (cp->pgno == pgno)
1345                                         cp->indx = indx;
1346                                 F_CLR(cp, C_REPLACE_SETUP);
1347                         }
1348                 }
1349                 break;
1350         }
1351         DB_THREAD_UNLOCK(dbp);
1352 }
1353
1354 /*
1355  * __bam_ca_split --
1356  *      Adjust the cursors when splitting a page.
1357  *
1358  * PUBLIC: void __bam_ca_split __P((DB *,
1359  * PUBLIC:    db_pgno_t, db_pgno_t, db_pgno_t, u_int32_t, int));
1360  */
1361 void
1362 __bam_ca_split(dbp, ppgno, lpgno, rpgno, split_indx, cleft)
1363         DB *dbp;
1364         db_pgno_t ppgno, lpgno, rpgno;
1365         u_int32_t split_indx;
1366         int cleft;
1367 {
1368         DBC *dbc;
1369         CURSOR *cp;
1370
1371         /* Recno is responsible for its own adjustments. */
1372         if (dbp->type == DB_RECNO)
1373                 return;
1374
1375         /*
1376          * Adjust the cursors.  See the comment in __bam_ca_delete().
1377          *
1378          * If splitting the page that a cursor was on, the cursor has to be
1379          * adjusted to point to the same record as before the split.  Most
1380          * of the time we don't adjust pointers to the left page, because
1381          * we're going to copy its contents back over the original page.  If
1382          * the cursor is on the right page, it is decremented by the number of
1383          * records split to the left page.
1384          */
1385         DB_THREAD_LOCK(dbp);
1386         for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1387             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1388                 cp = (CURSOR *)dbc->internal;
1389                 if (cp->pgno == ppgno)
1390                         if (cp->indx < split_indx) {
1391                                 if (cleft)
1392                                         cp->pgno = lpgno;
1393                         } else {
1394                                 cp->pgno = rpgno;
1395                                 cp->indx -= split_indx;
1396                         }
1397                 if (cp->dpgno == ppgno)
1398                         if (cp->dindx < split_indx) {
1399                                 if (cleft)
1400                                         cp->dpgno = lpgno;
1401                         } else {
1402                                 cp->dpgno = rpgno;
1403                                 cp->dindx -= split_indx;
1404                         }
1405         }
1406         DB_THREAD_UNLOCK(dbp);
1407 }
1408
1409 /*
1410  * __bam_c_physdel --
1411  *      Actually do the cursor deletion.
1412  */
1413 static int
1414 __bam_c_physdel(dbp, cp, h)
1415         DB *dbp;
1416         CURSOR *cp;
1417         PAGE *h;
1418 {
1419         BOVERFLOW bo;
1420         BTREE *t;
1421         DBT dbt;
1422         DB_LOCK lock;
1423         db_indx_t indx;
1424         db_pgno_t pgno, next_pgno, prev_pgno;
1425         int local, ret;
1426
1427         t = dbp->internal;
1428         ret = 0;
1429
1430         /* Figure out what we're deleting. */
1431         if (cp->dpgno == PGNO_INVALID) {
1432                 pgno = cp->pgno;
1433                 indx = cp->indx;
1434         } else {
1435                 pgno = cp->dpgno;
1436                 indx = cp->dindx;
1437         }
1438
1439         /*
1440          * If the item is referenced by another cursor, leave it up to that
1441          * cursor to do the delete.
1442          */
1443         if (__bam_ca_delete(dbp, pgno, indx, cp) != 0)
1444                 return (0);
1445
1446         /*
1447          * If we don't already have the page locked, get it and delete the
1448          * items.
1449          */
1450         if ((h == NULL || h->pgno != pgno)) {
1451                 if ((ret = __bam_lget(dbp, 0, pgno, DB_LOCK_WRITE, &lock)) != 0)
1452                         return (ret);
1453                 if ((ret = __bam_pget(dbp, &h, &pgno, 0)) != 0)
1454                         return (ret);
1455                 local = 1;
1456         } else
1457                 local = 0;
1458
1459         /*
1460          * If we're deleting a duplicate entry, call the common code to do
1461          * the work.
1462          */
1463         if (TYPE(h) == P_DUPLICATE) {
1464                 pgno = PGNO(h);
1465                 prev_pgno = PREV_PGNO(h);
1466                 next_pgno = NEXT_PGNO(h);
1467                 if ((ret = __db_drem(dbp, &h, indx, __bam_free)) != 0)
1468                         goto err;
1469
1470                 /*
1471                  * There are 4 cases:
1472                  *
1473                  * 1. We removed an item on a page, but there are more items
1474                  *    on the page.
1475                  * 2. We removed the last item on a page, removing the last
1476                  *    duplicate.
1477                  * 3. We removed the last item on a page, but there is a
1478                  *    following page of duplicates.
1479                  * 4. We removed the last item on a page, but there is a
1480                  *    previous page of duplicates.
1481                  *
1482                  * In case 1, h != NULL, h->pgno == pgno
1483                  * In case 2, h == NULL,
1484                  *    prev_pgno == PGNO_INVALID, next_pgno == PGNO_INVALID
1485                  * In case 3, h != NULL, next_pgno != PGNO_INVALID
1486                  * In case 4, h == NULL, prev_pgno != PGNO_INVALID
1487                  *
1488                  * In case 1, there's nothing else to do.
1489                  * In case 2, remove the entry from the parent page.
1490                  * In case 3 or 4, if the deleted page was the first in a chain
1491                  *    of duplicate pages, update the parent page's entry.
1492                  *
1493                  * Test:
1494                  *      If there were previous pages of duplicates or we didn't
1495                  *      empty the current page of duplicates, we don't need to
1496                  *      touch the parent page.
1497                  */
1498                 if (prev_pgno != PGNO_INVALID || (h != NULL && pgno == h->pgno))
1499                         goto done;
1500
1501                 /*
1502                  * Release any page we're holding and the lock on the deleted
1503                  * page.
1504                  */
1505                 if (local) {
1506                         if (h != NULL)
1507                                 (void)memp_fput(dbp->mpf, h, 0);
1508                         (void)__BT_TLPUT(dbp, lock);
1509                         local = 0;
1510                 }
1511
1512                 /* Acquire the parent page. */
1513                 if ((ret =
1514                     __bam_lget(dbp, 0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
1515                         goto err;
1516                 if ((ret = __bam_pget(dbp, &h, &cp->pgno, 0)) != 0) {
1517                         (void)__BT_TLPUT(dbp, lock);
1518                         goto err;
1519                 }
1520                 local = 1;
1521
1522                 /*
1523                  * If we deleted the last duplicate, we can fall out and do a
1524                  * normal btree delete in the context of the parent page.  If
1525                  * not, we have to update the parent's page.
1526                  */
1527                 indx = cp->indx;
1528                 if (next_pgno != PGNO_INVALID) {
1529                         /*
1530                          * Copy, delete, update and re-insert the parent page's
1531                          * entry.
1532                          */
1533                         bo = *GET_BOVERFLOW(h, indx);
1534                         (void)__db_ditem(dbp, h, indx, BOVERFLOW_SIZE);
1535                         bo.pgno = next_pgno;
1536                         memset(&dbt, 0, sizeof(dbt));
1537                         dbt.data = &bo;
1538                         dbt.size = BOVERFLOW_SIZE;
1539                         (void)__db_pitem(dbp,
1540                             h, indx, BOVERFLOW_SIZE, &dbt, NULL);
1541
1542                         /* Discard the parent page. */
1543                         (void)memp_fput(dbp->mpf, h, 0);
1544                         (void)__BT_TLPUT(dbp, lock);
1545                         local = 0;
1546
1547                         goto done;
1548                 }
1549         }
1550
1551         /* Otherwise, do a normal btree delete. */
1552         if ((ret = __bam_ditem(dbp, h, indx)) != 0)
1553                 goto err;
1554         if ((ret = __bam_ditem(dbp, h, indx)) != 0)
1555                 goto err;
1556
1557         /*
1558          * If the page is empty, delete it.  To delete a leaf page we need a
1559          * copy of a key from the page.  We use the first one that was there,
1560          * since it's the last key that the page held.  We malloc the page
1561          * information instead of using the return key/data memory because
1562          * we've already set them -- the reason that we've already set them
1563          * is because we're (potentially) about to do a reverse split, which
1564          * would make our saved page information useless.
1565          *
1566          * XXX
1567          * The following operations to delete a page might deadlock.  I think
1568          * that's OK.  The problem is if we're deleting an item because we're
1569          * closing cursors because we've already deadlocked and want to call
1570          * txn_abort().  If we fail due to deadlock, we'll leave an locked
1571          * empty page in the tree, which won't be empty long because we're
1572          * going to undo the delete.
1573          */
1574         if (NUM_ENT(h) == 0 && h->pgno != PGNO_ROOT) {
1575                 memset(&dbt, 0, sizeof(DBT));
1576                 dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
1577                 if ((ret = __db_ret(dbp, h, 0, &dbt, NULL, NULL)) != 0)
1578                         goto err;
1579
1580                 if (local) {
1581                         (void)memp_fput(dbp->mpf, h, 0);
1582                         (void)__BT_TLPUT(dbp, lock);
1583                         local = 0;
1584                 }
1585
1586                 ret = __bam_dpage(dbp, &dbt);
1587                 free(dbt.data);
1588         }
1589
1590 err:
1591 done:   if (local) {
1592                 (void)memp_fput(dbp->mpf, h, 0);
1593                 (void)__BT_TLPUT(dbp, lock);
1594         }
1595
1596         if (ret == 0)
1597                 ++t->lstat.bt_deleted;
1598         return (ret);
1599 }