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