db2/btree/bt_cursor.c

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