bt_cursor.c
上传用户:tsgydb
上传日期:2007-04-14
资源大小:10674k
文件大小:56k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*-
  2.  * See the file LICENSE for redistribution information.
  3.  *
  4.  * Copyright (c) 1996, 1997, 1998, 1999, 2000
  5.  * Sleepycat Software.  All rights reserved.
  6.  */
  7. #include "db_config.h"
  8. #ifndef lint
  9. static const char revid[] = "$Id: bt_cursor.c,v 11.88 2001/01/11 18:19:49 bostic Exp $";
  10. #endif /* not lint */
  11. #ifndef NO_SYSTEM_INCLUDES
  12. #include <sys/types.h>
  13. #include <stdlib.h>
  14. #include <string.h>
  15. #endif
  16. #include "db_int.h"
  17. #include "db_page.h"
  18. #include "db_shash.h"
  19. #include "btree.h"
  20. #include "lock.h"
  21. #include "qam.h"
  22. #include "common_ext.h"
  23. static int  __bam_c_close __P((DBC *, db_pgno_t, int *));
  24. static int  __bam_c_del __P((DBC *));
  25. static int  __bam_c_destroy __P((DBC *));
  26. static int  __bam_c_first __P((DBC *));
  27. static int  __bam_c_get __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *));
  28. static int  __bam_c_getstack __P((DBC *));
  29. static int  __bam_c_last __P((DBC *));
  30. static int  __bam_c_next __P((DBC *, int));
  31. static int  __bam_c_physdel __P((DBC *));
  32. static int  __bam_c_prev __P((DBC *));
  33. static int  __bam_c_put __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *));
  34. static void __bam_c_reset __P((BTREE_CURSOR *));
  35. static int  __bam_c_search __P((DBC *, const DBT *, u_int32_t, int *));
  36. static int  __bam_c_writelock __P((DBC *));
  37. static int  __bam_getboth_finddatum __P((DBC *, DBT *));
  38. static int  __bam_getbothc __P((DBC *, DBT *));
  39. static int  __bam_isopd __P((DBC *, db_pgno_t *));
  40. /*
  41.  * Acquire a new page/lock.  If we hold a page/lock, discard the page, and
  42.  * lock-couple the lock.
  43.  *
  44.  * !!!
  45.  * We have to handle both where we have a lock to lock-couple and where we
  46.  * don't -- we don't duplicate locks when we duplicate cursors if we are
  47.  * running in a transaction environment as there's no point if locks are
  48.  * never discarded.  This means that the cursor may or may not hold a lock.
  49.  */
  50. #undef ACQUIRE
  51. #define ACQUIRE(dbc, mode, lpgno, lock, fpgno, pagep, ret) {
  52. if ((pagep) != NULL) {
  53. ret = memp_fput((dbc)->dbp->mpf, pagep, 0);
  54. pagep = NULL;
  55. } else
  56. ret = 0;
  57. if ((ret) == 0 && STD_LOCKING(dbc))
  58. ret = __db_lget(dbc,
  59.     (lock).off == LOCK_INVALID ? 0 : LCK_COUPLE,
  60.     lpgno, mode, 0, &lock);
  61. else
  62. (lock).off = LOCK_INVALID;
  63. if ((ret) == 0)
  64. ret = memp_fget((dbc)->dbp->mpf, &(fpgno), 0, &(pagep));
  65. }
  66. /* Acquire a new page/lock for a cursor. */
  67. #undef ACQUIRE_CUR
  68. #define ACQUIRE_CUR(dbc, mode, ret) {
  69. BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal;
  70. ACQUIRE(dbc, mode,
  71.     __cp->pgno, __cp->lock, __cp->pgno, __cp->page, ret);
  72. if ((ret) == 0)
  73. __cp->lock_mode = (mode);
  74. }
  75. /*
  76.  * Acquire a new page/lock for a cursor, and move the cursor on success.
  77.  * The reason that this is a separate macro is because we don't want to
  78.  * set the pgno/indx fields in the cursor until we actually have the lock,
  79.  * otherwise the cursor adjust routines will adjust the cursor even though
  80.  * we're not really on the page.
  81.  */
  82. #undef ACQUIRE_CUR_SET
  83. #define ACQUIRE_CUR_SET(dbc, mode, p, ret) {
  84. BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal;
  85. ACQUIRE(dbc, mode, p, __cp->lock, p, __cp->page, ret);
  86. if ((ret) == 0) {
  87. __cp->pgno = p;
  88. __cp->indx = 0;
  89. __cp->lock_mode = (mode);
  90. }
  91. }
  92. /*
  93.  * Acquire a write lock if we don't already have one.
  94.  *
  95.  * !!!
  96.  * See ACQUIRE macro on why we handle cursors that don't have locks.
  97.  */
  98. #undef ACQUIRE_WRITE_LOCK
  99. #define ACQUIRE_WRITE_LOCK(dbc, ret) {
  100. BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal;
  101. ret = 0;
  102. if (STD_LOCKING(dbc) &&
  103.     __cp->lock_mode != DB_LOCK_WRITE &&
  104.     ((ret) = __db_lget(dbc,
  105.     __cp->lock.off == LOCK_INVALID ? 0 : LCK_COUPLE,
  106.     __cp->pgno, DB_LOCK_WRITE, 0, &__cp->lock)) == 0)
  107. __cp->lock_mode = DB_LOCK_WRITE;
  108. }
  109. /* Discard the current page/lock. */
  110. #undef DISCARD
  111. #define DISCARD(dbc, ldiscard, lock, pagep, ret) {
  112. int __t_ret;
  113. if ((pagep) != NULL) {
  114. ret = memp_fput((dbc)->dbp->mpf, pagep, 0);
  115. pagep = NULL;
  116. } else
  117. ret = 0;
  118. if ((lock).off != LOCK_INVALID) {
  119. __t_ret = ldiscard ?
  120.     __LPUT((dbc), lock): __TLPUT((dbc), lock);
  121. if (__t_ret != 0 && (ret) == 0)
  122. ret = __t_ret;
  123. (lock).off = LOCK_INVALID;
  124. }
  125. }
  126. /* Discard the current page/lock for a cursor. */
  127. #undef DISCARD_CUR
  128. #define DISCARD_CUR(dbc, ret) {
  129. BTREE_CURSOR *__cp = (BTREE_CURSOR *)(dbc)->internal;
  130. DISCARD(dbc, 0, __cp->lock, __cp->page, ret);
  131. if ((ret) == 0)
  132. __cp->lock_mode = DB_LOCK_NG;
  133. }
  134. /* If on-page item is a deleted record. */
  135. #undef IS_DELETED
  136. #define IS_DELETED(page, indx)
  137. B_DISSET(GET_BKEYDATA(page,
  138.     (indx) + (TYPE(page) == P_LBTREE ? O_INDX : 0))->type)
  139. #undef IS_CUR_DELETED
  140. #define IS_CUR_DELETED(dbc)
  141. IS_DELETED((dbc)->internal->page, (dbc)->internal->indx)
  142. /*
  143.  * Test to see if two cursors could point to duplicates of the same key.
  144.  * In the case of off-page duplicates they are they same, as the cursors
  145.  * will be in the same off-page duplicate tree.  In the case of on-page
  146.  * duplicates, the key index offsets must be the same.  For the last test,
  147.  * as the original cursor may not have a valid page pointer, we use the
  148.  * current cursor's.
  149.  */
  150. #undef IS_DUPLICATE
  151. #define IS_DUPLICATE(dbc, i1, i2)
  152.     (((PAGE *)(dbc)->internal->page)->inp[i1] ==
  153.      ((PAGE *)(dbc)->internal->page)->inp[i2])
  154. #undef IS_CUR_DUPLICATE
  155. #define IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx)
  156. (F_ISSET(dbc, DBC_OPD) ||
  157.     (orig_pgno == (dbc)->internal->pgno &&
  158.     IS_DUPLICATE(dbc, (dbc)->internal->indx, orig_indx)))
  159. /*
  160.  * __bam_c_reset --
  161.  * Initialize internal cursor structure.
  162.  */
  163. static void
  164. __bam_c_reset(cp)
  165. BTREE_CURSOR *cp;
  166. {
  167. cp->csp = cp->sp;
  168. cp->lock.off = LOCK_INVALID;
  169. cp->lock_mode = DB_LOCK_NG;
  170. cp->recno = RECNO_OOB;
  171. cp->order = INVALID_ORDER;
  172. cp->flags = 0;
  173. }
  174. /*
  175.  * __bam_c_init --
  176.  * Initialize the access private portion of a cursor
  177.  *
  178.  * PUBLIC: int __bam_c_init __P((DBC *, DBTYPE));
  179.  */
  180. int
  181. __bam_c_init(dbc, dbtype)
  182. DBC *dbc;
  183. DBTYPE dbtype;
  184. {
  185. BTREE *t;
  186. BTREE_CURSOR *cp;
  187. DB *dbp;
  188. int ret;
  189. u_int32_t minkey;
  190. dbp = dbc->dbp;
  191. /* Allocate/initialize the internal structure. */
  192. if (dbc->internal == NULL) {
  193. if ((ret = __os_malloc(dbp->dbenv,
  194.     sizeof(BTREE_CURSOR), NULL, &cp)) != 0)
  195. return (ret);
  196. dbc->internal = (DBC_INTERNAL *)cp;
  197. cp->sp = cp->csp = cp->stack;
  198. cp->esp = cp->stack + sizeof(cp->stack) / sizeof(cp->stack[0]);
  199. } else
  200. cp = (BTREE_CURSOR *)dbc->internal;
  201. __bam_c_reset(cp);
  202. /* Initialize methods. */
  203. dbc->c_close = __db_c_close;
  204. dbc->c_count = __db_c_count;
  205. dbc->c_del = __db_c_del;
  206. dbc->c_dup = __db_c_dup;
  207. dbc->c_get = __db_c_get;
  208. dbc->c_put = __db_c_put;
  209. if (dbtype == DB_BTREE) {
  210. dbc->c_am_close = __bam_c_close;
  211. dbc->c_am_del = __bam_c_del;
  212. dbc->c_am_destroy = __bam_c_destroy;
  213. dbc->c_am_get = __bam_c_get;
  214. dbc->c_am_put = __bam_c_put;
  215. dbc->c_am_writelock = __bam_c_writelock;
  216. } else {
  217. dbc->c_am_close = __bam_c_close;
  218. dbc->c_am_del = __ram_c_del;
  219. dbc->c_am_destroy = __bam_c_destroy;
  220. dbc->c_am_get = __ram_c_get;
  221. dbc->c_am_put = __ram_c_put;
  222. dbc->c_am_writelock = __bam_c_writelock;
  223. }
  224. /*
  225.  * The btree leaf page data structures require that two key/data pairs
  226.  * (or four items) fit on a page, but other than that there's no fixed
  227.  * requirement.  The btree off-page duplicates only require two items,
  228.  * to be exact, but requiring four for them as well seems reasonable.
  229.  *
  230.  * Recno uses the btree bt_ovflsize value -- it's close enough.
  231.  */
  232. t = dbp->bt_internal;
  233. minkey = F_ISSET(dbc, DBC_OPD) ? 2 : t->bt_minkey;
  234. cp->ovflsize = B_MINKEY_TO_OVFLSIZE(minkey, dbp->pgsize);
  235. return (0);
  236. }
  237. /*
  238.  * __bam_c_refresh
  239.  * Set things up properly for cursor re-use.
  240.  *
  241.  * PUBLIC: int __bam_c_refresh __P((DBC *));
  242.  */
  243. int
  244. __bam_c_refresh(dbc)
  245. DBC *dbc;
  246. {
  247. BTREE_CURSOR *cp;
  248. DB *dbp;
  249. dbp = dbc->dbp;
  250. cp = (BTREE_CURSOR *)dbc->internal;
  251. __bam_c_reset(cp);
  252. /*
  253.  * If our caller set the root page number, it's because the root was
  254.  * known.  This is always the case for off page dup cursors.  Else,
  255.  * pull it out of our internal information.
  256.  */
  257. if (cp->root == PGNO_INVALID)
  258. cp->root = ((BTREE *)dbp->bt_internal)->bt_root;
  259. /* Initialize for record numbers. */
  260. if (F_ISSET(dbc, DBC_OPD) ||
  261.     dbc->dbtype == DB_RECNO || F_ISSET(dbp, DB_BT_RECNUM)) {
  262. F_SET(cp, C_RECNUM);
  263. /*
  264.  * All btrees that support record numbers, optionally standard
  265.  * recno trees, and all off-page duplicate recno trees have
  266.  * mutable record numbers.
  267.  */
  268. if ((F_ISSET(dbc, DBC_OPD) && dbc->dbtype == DB_RECNO) ||
  269.     F_ISSET(dbp, DB_BT_RECNUM | DB_RE_RENUMBER))
  270. F_SET(cp, C_RENUMBER);
  271. }
  272. return (0);
  273. }
  274. /*
  275.  * __bam_c_close --
  276.  * Close down the cursor.
  277.  */
  278. static int
  279. __bam_c_close(dbc, root_pgno, rmroot)
  280. DBC *dbc;
  281. db_pgno_t root_pgno;
  282. int *rmroot;
  283. {
  284. BTREE_CURSOR *cp, *cp_opd, *cp_c;
  285. DB *dbp;
  286. DBC *dbc_opd, *dbc_c;
  287. PAGE *h;
  288. u_int32_t num;
  289. int cdb_lock, ret, t_ret;
  290. dbp = dbc->dbp;
  291. cp = (BTREE_CURSOR *)dbc->internal;
  292. cp_opd = (dbc_opd = cp->opd) == NULL ?
  293.     NULL : (BTREE_CURSOR *)dbc_opd->internal;
  294. cdb_lock = ret = 0;
  295. /*
  296.  * There are 3 ways this function is called:
  297.  *
  298.  * 1. Closing a primary cursor: we get called with a pointer to a
  299.  *    primary cursor that has a NULL opd field.  This happens when
  300.  *    closing a btree/recno database cursor without an associated
  301.  *    off-page duplicate tree.
  302.  *
  303.  * 2. Closing a primary and an off-page duplicate cursor stack: we
  304.  *    get called with a pointer to the primary cursor which has a
  305.  *    non-NULL opd field.  This happens when closing a btree cursor
  306.  *    into database with an associated off-page btree/recno duplicate
  307.  *    tree. (It can't be a primary recno database, recno databases
  308.  *    don't support duplicates.)
  309.  *
  310.  * 3. Closing an off-page duplicate cursor stack: we get called with
  311.  *    a pointer to the off-page duplicate cursor.  This happens when
  312.  *    closing a non-btree database that has an associated off-page
  313.  *    btree/recno duplicate tree or for a btree database when the
  314.  *    opd tree is not empty (root_pgno == PGNO_INVALID).
  315.  *
  316.  * If either the primary or off-page duplicate cursor deleted a btree
  317.  * key/data pair, check to see if the item is still referenced by a
  318.  * different cursor.  If it is, confirm that cursor's delete flag is
  319.  * set and leave it to that cursor to do the delete.
  320.  *
  321.  * NB: The test for == 0 below is correct.  Our caller already removed
  322.  * our cursor argument from the active queue, we won't find it when we
  323.  * search the queue in __bam_ca_delete().
  324.  * NB: It can't be true that both the primary and off-page duplicate
  325.  * cursors have deleted a btree key/data pair.  Either the primary
  326.  * cursor may have deleted an item and there's no off-page duplicate
  327.  * cursor, or there's an off-page duplicate cursor and it may have
  328.  * deleted an item.
  329.  *
  330.  * Primary recno databases aren't an issue here.  Recno keys are either
  331.  * deleted immediately or never deleted, and do not have to be handled
  332.  * here.
  333.  *
  334.  * Off-page duplicate recno databases are an issue here, cases #2 and
  335.  * #3 above can both be off-page recno databases.  The problem is the
  336.  * same as the final problem for off-page duplicate btree databases.
  337.  * If we no longer need the off-page duplicate tree, we want to remove
  338.  * it.  For off-page duplicate btrees, we are done with the tree when
  339.  * we delete the last item it contains, i.e., there can be no further
  340.  * references to it when it's empty.  For off-page duplicate recnos,
  341.  * we remove items from the tree as the application calls the remove
  342.  * function, so we are done with the tree when we close the last cursor
  343.  * that references it.
  344.  *
  345.  * We optionally take the root page number from our caller.  If the
  346.  * primary database is a btree, we can get it ourselves because dbc
  347.  * is the primary cursor.  If the primary database is not a btree,
  348.  * the problem is that we may be dealing with a stack of pages.  The
  349.  * cursor we're using to do the delete points at the bottom of that
  350.  * stack and we need the top of the stack.
  351.  */
  352. if (F_ISSET(cp, C_DELETED)) {
  353. dbc_c = dbc;
  354. switch (dbc->dbtype) {
  355. case DB_BTREE: /* Case #1, #3. */
  356. if (__bam_ca_delete(dbp, cp->pgno, cp->indx, 1) == 0)
  357. goto lock;
  358. goto done;
  359. case DB_RECNO:
  360. if (!F_ISSET(dbc, DBC_OPD)) /* Case #1. */
  361. goto done;
  362. /* Case #3. */
  363. if (__ram_ca_delete(dbp, cp->root) == 0)
  364. goto lock;
  365. goto done;
  366. default:
  367. return (__db_unknown_type(dbp->dbenv,
  368. "__bam_c_close", dbc->dbtype));
  369. }
  370. }
  371. if (dbc_opd == NULL)
  372. goto done;
  373. if (F_ISSET(cp_opd, C_DELETED)) { /* Case #2. */
  374. /*
  375.  * We will not have been provided a root page number.  Acquire
  376.  * one from the primary database.
  377.  */
  378. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &h)) != 0)
  379. goto err;
  380. root_pgno = GET_BOVERFLOW(h, cp->indx + O_INDX)->pgno;
  381. if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
  382. goto err;
  383. dbc_c = dbc_opd;
  384. switch (dbc_opd->dbtype) {
  385. case DB_BTREE:
  386. if (__bam_ca_delete(
  387.     dbp, cp_opd->pgno, cp_opd->indx, 1) == 0)
  388. goto lock;
  389. goto done;
  390. case DB_RECNO:
  391. if (__ram_ca_delete(dbp, cp_opd->root) == 0)
  392. goto lock;
  393. goto done;
  394. default:
  395. return (__db_unknown_type(dbp->dbenv,
  396. "__bam_c_close", dbc->dbtype));
  397. }
  398. }
  399. goto done;
  400. lock: cp_c = (BTREE_CURSOR *)dbc_c->internal;
  401. /*
  402.  * If this is CDB, upgrade the lock if necessary.  While we acquired
  403.  * the write lock to logically delete the record, we released it when
  404.  * we returned from that call, and so may not be holding a write lock
  405.  * at the moment.  NB: to get here in CDB we must either be holding a
  406.  * write lock or be the only cursor that is permitted to acquire write
  407.  * locks.  The reason is that there can never be more than a single CDB
  408.  * write cursor (that cursor cannot be dup'd), and so that cursor must
  409.  * be closed and the item therefore deleted before any other cursor
  410.  * could acquire a reference to this item.
  411.  *
  412.  * Note that dbc may be an off-page dup cursor;  this is the sole
  413.  * instance in which an OPD cursor does any locking, but it's necessary
  414.  * because we may be closed by ourselves without a parent cursor
  415.  * handy, and we have to do a lock upgrade on behalf of somebody.
  416.  * If this is the case, the OPD has been given the parent's locking
  417.  * info in __db_c_get--the OPD is also a WRITEDUP.
  418.  */
  419. if (CDB_LOCKING(dbp->dbenv)) {
  420. DB_ASSERT(!F_ISSET(dbc, DBC_OPD) || F_ISSET(dbc, DBC_WRITEDUP));
  421. if (!F_ISSET(dbc, DBC_WRITER)) {
  422. if ((ret =
  423.     lock_get(dbp->dbenv, dbc->locker, DB_LOCK_UPGRADE,
  424.     &dbc->lock_dbt, DB_LOCK_WRITE, &dbc->mylock)) != 0)
  425. goto err;
  426. cdb_lock = 1;
  427. }
  428. cp_c->lock.off = LOCK_INVALID;
  429. if ((ret =
  430.     memp_fget(dbp->mpf, &cp_c->pgno, 0, &cp_c->page)) != 0)
  431. goto err;
  432. goto delete;
  433. }
  434. /*
  435.  * The variable dbc_c has been initialized to reference the cursor in
  436.  * which we're going to do the delete.  Initialize the cursor's page
  437.  * and lock structures as necessary.
  438.  *
  439.  * First, we may not need to acquire any locks.  If we're in case #3,
  440.  * that is, the primary database isn't a btree database, our caller
  441.  * is responsible for acquiring any necessary locks before calling us.
  442.  */
  443. if (F_ISSET(dbc, DBC_OPD)) {
  444. cp_c->lock.off = LOCK_INVALID;
  445. if ((ret =
  446.     memp_fget(dbp->mpf, &cp_c->pgno, 0, &cp_c->page)) != 0)
  447. goto err;
  448. goto delete;
  449. }
  450. /*
  451.  * Otherwise, acquire a write lock.  If the cursor that did the initial
  452.  * logical deletion (and which had a write lock) is not the same as the
  453.  * cursor doing the physical deletion (which may have only ever had a
  454.  * read lock on the item), we need to upgrade.  The confusion comes as
  455.  * follows:
  456.  *
  457.  * C1 created, acquires item read lock
  458.  * C2 dup C1, create C2, also has item read lock.
  459.  * C1 acquire write lock, delete item
  460.  * C1 close
  461.  * C2 close, needs a write lock to physically delete item.
  462.  *
  463.  * If we're in a TXN, we know that C2 will be able to acquire the write
  464.  * lock, because no locker other than the one shared by C1 and C2 can
  465.  * acquire a write lock -- the original write lock C1 acquire was never
  466.  * discarded.
  467.  *
  468.  * If we're not in a TXN, it's nastier.  Other cursors might acquire
  469.  * read locks on the item after C1 closed, discarding its write lock,
  470.  * and such locks would prevent C2 from acquiring a read lock.  That's
  471.  * OK, though, we'll simply wait until we can acquire a read lock, or
  472.  * we'll deadlock.  (Which better not happen, since we're not in a TXN.)
  473.  *
  474.  * Lock the primary database page, regardless of whether we're deleting
  475.  * an item on a primary database page or an off-page duplicates page.
  476.  */
  477. ACQUIRE(dbc, DB_LOCK_WRITE,
  478.     cp->pgno, cp_c->lock, cp_c->pgno, cp_c->page, ret);
  479. if (ret != 0)
  480. goto err;
  481. delete: /*
  482.  * If the delete occurred in a btree, delete the on-page physical item
  483.  * referenced by the cursor.
  484.  */
  485. if (dbc_c->dbtype == DB_BTREE && (ret = __bam_c_physdel(dbc_c)) != 0)
  486. goto err;
  487. /*
  488.  * If we're not working in an off-page duplicate tree, then we're
  489.  * done.
  490.  */
  491. if (!F_ISSET(dbc_c, DBC_OPD) || root_pgno == PGNO_INVALID)
  492. goto done;
  493. /*
  494.  * We may have just deleted the last element in the off-page duplicate
  495.  * tree, and closed the last cursor in the tree.  For an off-page btree
  496.  * there are no other cursors in the tree by definition, if the tree is
  497.  * empty.  For an off-page recno we know we have closed the last cursor
  498.  * in the tree because the __ram_ca_delete call above returned 0 only
  499.  * in that case.  So, if the off-page duplicate tree is empty at this
  500.  * point, we want to remove it.
  501.  */
  502. if ((ret = memp_fget(dbp->mpf, &root_pgno, 0, &h)) != 0)
  503. goto err;
  504. if ((num = NUM_ENT(h)) == 0) {
  505. if ((ret = __db_free(dbc, h)) != 0)
  506. goto err;
  507. } else {
  508. if ((ret = memp_fput(dbp->mpf, h, 0)) != 0)
  509. goto err;
  510. goto done;
  511. }
  512. /*
  513.  * When removing the tree, we have to do one of two things.  If this is
  514.  * case #2, that is, the primary tree is a btree, delete the key that's
  515.  * associated with the tree from the btree leaf page.  We know we are
  516.  * the only reference to it and we already have the correct lock.  We
  517.  * detect this case because the cursor that was passed to us references
  518.  * an off-page duplicate cursor.
  519.  *
  520.  * If this is case #3, that is, the primary tree isn't a btree, pass
  521.  * the information back to our caller, it's their job to do cleanup on
  522.  * the primary page.
  523.  */
  524. if (dbc_opd != NULL) {
  525. cp->lock.off = LOCK_INVALID;
  526. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
  527. goto err;
  528. if ((ret = __bam_c_physdel(dbc)) != 0)
  529. goto err;
  530. } else
  531. *rmroot = 1;
  532. err:
  533. done: /*
  534.  * Discard the page references and locks, and confirm that the stack
  535.  * has been emptied.
  536.  */
  537. if (dbc_opd != NULL) {
  538. DISCARD_CUR(dbc_opd, t_ret);
  539. if (t_ret != 0 && ret == 0)
  540. ret = t_ret;
  541. }
  542. DISCARD_CUR(dbc, t_ret);
  543. if (t_ret != 0 && ret == 0)
  544. ret = t_ret;
  545. /* Downgrade any CDB lock we acquired. */
  546. if (cdb_lock)
  547. (void)__lock_downgrade(
  548.     dbp->dbenv, &dbc->mylock, DB_LOCK_IWRITE, 0);
  549. return (ret);
  550. }
  551. /*
  552.  * __bam_c_destroy --
  553.  * Close a single cursor -- internal version.
  554.  */
  555. static int
  556. __bam_c_destroy(dbc)
  557. DBC *dbc;
  558. {
  559. /* Discard the structures. */
  560. __os_free(dbc->internal, sizeof(BTREE_CURSOR));
  561. return (0);
  562. }
  563. /*
  564.  * __bam_c_count --
  565.  * Return a count of on and off-page duplicates.
  566.  *
  567.  * PUBLIC: int __bam_c_count __P((DBC *, db_recno_t *));
  568.  */
  569. int
  570. __bam_c_count(dbc, recnop)
  571. DBC *dbc;
  572. db_recno_t *recnop;
  573. {
  574. BTREE_CURSOR *cp;
  575. DB *dbp;
  576. db_indx_t indx, top;
  577. db_recno_t recno;
  578. int ret;
  579. dbp = dbc->dbp;
  580. cp = (BTREE_CURSOR *)dbc->internal;
  581. /*
  582.  * Called with the top-level cursor that may reference an off-page
  583.  * duplicates page.  If it's a set of on-page duplicates, get the
  584.  * page and count.  Otherwise, get the root page of the off-page
  585.  * duplicate tree, and use the count.  We don't have to acquire any
  586.  * new locks, we have to have a read lock to even get here.
  587.  */
  588. if (cp->opd == NULL) {
  589. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
  590. return (ret);
  591. /*
  592.  * Move back to the beginning of the set of duplicates and
  593.  * then count forward.
  594.  */
  595. for (indx = cp->indx;; indx -= P_INDX)
  596. if (indx == 0 ||
  597.     !IS_DUPLICATE(dbc, indx, indx - P_INDX))
  598. break;
  599. for (recno = 1, top = NUM_ENT(cp->page) - P_INDX;
  600.     indx < top; ++recno, indx += P_INDX)
  601. if (!IS_DUPLICATE(dbc, indx, indx + P_INDX))
  602. break;
  603. *recnop = recno;
  604. } else {
  605. if ((ret = memp_fget(dbp->mpf,
  606.     &cp->opd->internal->root, 0, &cp->page)) != 0)
  607. return (ret);
  608. *recnop = RE_NREC(cp->page);
  609. }
  610. ret = memp_fput(dbp->mpf, cp->page, 0);
  611. cp->page = NULL;
  612. return (ret);
  613. }
  614. /*
  615.  * __bam_c_del --
  616.  * Delete using a cursor.
  617.  */
  618. static int
  619. __bam_c_del(dbc)
  620. DBC *dbc;
  621. {
  622. BTREE_CURSOR *cp;
  623. DB *dbp;
  624. int ret, t_ret;
  625. dbp = dbc->dbp;
  626. cp = (BTREE_CURSOR *)dbc->internal;
  627. ret = 0;
  628. /* If the item was already deleted, return failure. */
  629. if (F_ISSET(cp, C_DELETED))
  630. return (DB_KEYEMPTY);
  631. /*
  632.  * This code is always called with a page lock but no page.
  633.  */
  634. DB_ASSERT(cp->page == NULL);
  635. /*
  636.  * We don't physically delete the record until the cursor moves, so
  637.  * we have to have a long-lived write lock on the page instead of a
  638.  * a long-lived read lock.  Note, we have to have a read lock to even
  639.  * get here.
  640.  *
  641.  * If we're maintaining record numbers, we lock the entire tree, else
  642.  * we lock the single page.
  643.  */
  644. if (F_ISSET(cp, C_RECNUM)) {
  645. if ((ret = __bam_c_getstack(dbc)) != 0)
  646. goto err;
  647. cp->page = cp->csp->page;
  648. } else {
  649. ACQUIRE_CUR(dbc, DB_LOCK_WRITE, ret);
  650. if (ret != 0)
  651. goto err;
  652. }
  653. /* Log the change. */
  654. if (DB_LOGGING(dbc) &&
  655.     (ret = __bam_cdel_log(dbp->dbenv, dbc->txn, &LSN(cp->page), 0,
  656.     dbp->log_fileid, PGNO(cp->page), &LSN(cp->page), cp->indx)) != 0)
  657. goto err;
  658. /* Set the intent-to-delete flag on the page. */
  659. if (TYPE(cp->page) == P_LBTREE)
  660. B_DSET(GET_BKEYDATA(cp->page, cp->indx + O_INDX)->type);
  661. else
  662. B_DSET(GET_BKEYDATA(cp->page, cp->indx)->type);
  663. /* Mark the page dirty. */
  664. ret = memp_fset(dbp->mpf, cp->page, DB_MPOOL_DIRTY);
  665. err: /*
  666.  * If we've been successful so far and the tree has record numbers,
  667.  * adjust the record counts.  Either way, release acquired page(s).
  668.  */
  669. if (F_ISSET(cp, C_RECNUM)) {
  670. if (ret == 0)
  671. ret = __bam_adjust(dbc, -1);
  672. (void)__bam_stkrel(dbc, 0);
  673. } else
  674. if (cp->page != NULL &&
  675.     (t_ret = memp_fput(dbp->mpf, cp->page, 0)) != 0 && ret == 0)
  676. ret = t_ret;
  677. cp->page = NULL;
  678. /* Update the cursors last, after all chance of failure is past. */
  679. if (ret == 0)
  680. (void)__bam_ca_delete(dbp, cp->pgno, cp->indx, 1);
  681. return (ret);
  682. }
  683. /*
  684.  * __bam_c_dup --
  685.  * Duplicate a btree cursor, such that the new one holds appropriate
  686.  * locks for the position of the original.
  687.  *
  688.  * PUBLIC: int __bam_c_dup __P((DBC *, DBC *));
  689.  */
  690. int
  691. __bam_c_dup(orig_dbc, new_dbc)
  692. DBC *orig_dbc, *new_dbc;
  693. {
  694. BTREE_CURSOR *orig, *new;
  695. int ret;
  696. orig = (BTREE_CURSOR *)orig_dbc->internal;
  697. new = (BTREE_CURSOR *)new_dbc->internal;
  698. /*
  699.  * If we're holding a lock we need to acquire a copy of it, unless
  700.  * we're in a transaction.  We don't need to copy any lock we're
  701.  * holding inside a transaction because all the locks are retained
  702.  * until the transaction commits or aborts.
  703.  */
  704. if (orig->lock.off != LOCK_INVALID && orig_dbc->txn == NULL) {
  705. if ((ret = __db_lget(new_dbc,
  706.     0, new->pgno, new->lock_mode, 0, &new->lock)) != 0)
  707. return (ret);
  708. }
  709. new->ovflsize = orig->ovflsize;
  710. new->recno = orig->recno;
  711. new->flags = orig->flags;
  712. return (0);
  713. }
  714. /*
  715.  * __bam_c_get --
  716.  * Get using a cursor (btree).
  717.  */
  718. static int
  719. __bam_c_get(dbc, key, data, flags, pgnop)
  720. DBC *dbc;
  721. DBT *key, *data;
  722. u_int32_t flags;
  723. db_pgno_t *pgnop;
  724. {
  725. BTREE_CURSOR *cp;
  726. DB *dbp;
  727. db_pgno_t orig_pgno;
  728. db_indx_t orig_indx;
  729. int exact, newopd, ret;
  730. dbp = dbc->dbp;
  731. cp = (BTREE_CURSOR *)dbc->internal;
  732. orig_pgno = cp->pgno;
  733. orig_indx = cp->indx;
  734. newopd = 0;
  735. switch (flags) {
  736. case DB_CURRENT:
  737. /* It's not possible to return a deleted record. */
  738. if (F_ISSET(cp, C_DELETED)) {
  739. ret = DB_KEYEMPTY;
  740. goto err;
  741. }
  742. /*
  743.  * Acquire the current page.  We have at least a read-lock
  744.  * already.  The caller may have set DB_RMW asking for a
  745.  * write lock, but upgrading to a write lock has no better
  746.  * chance of succeeding now instead of later, so don't try.
  747.  */
  748. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
  749. goto err;
  750. break;
  751. case DB_FIRST:
  752. newopd = 1;
  753. if ((ret = __bam_c_first(dbc)) != 0)
  754. goto err;
  755. break;
  756. case DB_GET_BOTH:
  757. /*
  758.  * There are two ways to get here based on DBcursor->c_get
  759.  * with the DB_GET_BOTH flag set:
  760.  *
  761.  * 1. Searching a sorted off-page duplicate tree: do a tree
  762.  * search.
  763.  *
  764.  * 2. Searching btree: do a tree search.  If it returns a
  765.  * reference to off-page duplicate tree, return immediately
  766.  * and let our caller deal with it.  If the search doesn't
  767.  * return a reference to off-page duplicate tree, start an
  768.  * on-page search.
  769.  */
  770. if (F_ISSET(dbc, DBC_OPD)) {
  771. if ((ret = __bam_c_search(
  772.     dbc, data, DB_GET_BOTH, &exact)) != 0)
  773. goto err;
  774. if (!exact) {
  775. ret = DB_NOTFOUND;
  776. goto err;
  777. }
  778. } else {
  779. if ((ret = __bam_c_search(
  780.     dbc, key, DB_GET_BOTH, &exact)) != 0)
  781. return (ret);
  782. if (!exact) {
  783. ret = DB_NOTFOUND;
  784. goto err;
  785. }
  786. if (pgnop != NULL && __bam_isopd(dbc, pgnop)) {
  787. newopd = 1;
  788. break;
  789. }
  790. if ((ret = __bam_getboth_finddatum(dbc, data)) != 0)
  791. goto err;
  792. }
  793. break;
  794. case DB_GET_BOTHC:
  795. if ((ret = __bam_getbothc(dbc, data)) != 0)
  796. goto err;
  797. break;
  798. case DB_LAST:
  799. newopd = 1;
  800. if ((ret = __bam_c_last(dbc)) != 0)
  801. goto err;
  802. break;
  803. case DB_NEXT:
  804. newopd = 1;
  805. if (cp->pgno == PGNO_INVALID) {
  806. if ((ret = __bam_c_first(dbc)) != 0)
  807. goto err;
  808. } else
  809. if ((ret = __bam_c_next(dbc, 1)) != 0)
  810. goto err;
  811. break;
  812. case DB_NEXT_DUP:
  813. if ((ret = __bam_c_next(dbc, 1)) != 0)
  814. goto err;
  815. if (!IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx)) {
  816. ret = DB_NOTFOUND;
  817. goto err;
  818. }
  819. break;
  820. case DB_NEXT_NODUP:
  821. newopd = 1;
  822. if (cp->pgno == PGNO_INVALID) {
  823. if ((ret = __bam_c_first(dbc)) != 0)
  824. goto err;
  825. } else
  826. do {
  827. if ((ret = __bam_c_next(dbc, 1)) != 0)
  828. goto err;
  829. } while (IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx));
  830. break;
  831. case DB_PREV:
  832. newopd = 1;
  833. if (cp->pgno == PGNO_INVALID) {
  834. if ((ret = __bam_c_last(dbc)) != 0)
  835. goto err;
  836. } else
  837. if ((ret = __bam_c_prev(dbc)) != 0)
  838. goto err;
  839. break;
  840. case DB_PREV_NODUP:
  841. newopd = 1;
  842. if (cp->pgno == PGNO_INVALID) {
  843. if ((ret = __bam_c_last(dbc)) != 0)
  844. goto err;
  845. } else
  846. do {
  847. if ((ret = __bam_c_prev(dbc)) != 0)
  848. goto err;
  849. } while (IS_CUR_DUPLICATE(dbc, orig_pgno, orig_indx));
  850. break;
  851. case DB_SET:
  852. case DB_SET_RECNO:
  853. newopd = 1;
  854. if ((ret = __bam_c_search(dbc, key, flags, &exact)) != 0)
  855. goto err;
  856. break;
  857. case DB_SET_RANGE:
  858. newopd = 1;
  859. if ((ret = __bam_c_search(dbc, key, flags, &exact)) != 0)
  860. goto err;
  861. /*
  862.  * As we didn't require an exact match, the search function
  863.  * may have returned an entry past the end of the page.  Or,
  864.  * we may be referencing a deleted record.  If so, move to
  865.  * the next entry.
  866.  */
  867. if (cp->indx == NUM_ENT(cp->page) || IS_CUR_DELETED(dbc))
  868. if ((ret = __bam_c_next(dbc, 0)) != 0)
  869. goto err;
  870. break;
  871. default:
  872. ret = __db_unknown_flag(dbp->dbenv, "__bam_c_get", flags);
  873. goto err;
  874. }
  875. /*
  876.  * We may have moved to an off-page duplicate tree.  Return that
  877.  * information to our caller.
  878.  */
  879. if (newopd && pgnop != NULL)
  880. (void)__bam_isopd(dbc, pgnop);
  881. /* Don't return the key, it was passed to us */
  882. if (flags == DB_SET)
  883. F_SET(key, DB_DBT_ISSET);
  884. err: /*
  885.  * Regardless of whether we were successful or not, if the cursor
  886.  * moved, clear the delete flag, DBcursor->c_get never references
  887.  * a deleted key, if it moved at all.
  888.  */
  889. if (F_ISSET(cp, C_DELETED)
  890.     && (cp->pgno != orig_pgno || cp->indx != orig_indx))
  891. F_CLR(cp, C_DELETED);
  892. return (ret);
  893. }
  894. /*
  895.  * __bam_getbothc --
  896.  * Search for a matching data item on a join.
  897.  */
  898. static int
  899. __bam_getbothc(dbc, data)
  900. DBC *dbc;
  901. DBT *data;
  902. {
  903. BTREE_CURSOR *cp;
  904. DB *dbp;
  905. int cmp, exact, ret;
  906. dbp = dbc->dbp;
  907. cp = (BTREE_CURSOR *)dbc->internal;
  908. /*
  909.  * Acquire the current page.  We have at least a read-lock
  910.  * already.  The caller may have set DB_RMW asking for a
  911.  * write lock, but upgrading to a write lock has no better
  912.  * chance of succeeding now instead of later, so don't try.
  913.  */
  914. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
  915. return (ret);
  916. /*
  917.  * An off-page duplicate cursor.  Search the remaining duplicates
  918.  * for one which matches (do a normal btree search, then verify
  919.  * that the retrieved record is greater than the original one).
  920.  */
  921. if (F_ISSET(dbc, DBC_OPD)) {
  922. /*
  923.  * Check to make sure the desired item comes strictly after
  924.  * the current position;  if it doesn't, return DB_NOTFOUND.
  925.  */
  926. if ((ret = __bam_cmp(dbp, data, cp->page, cp->indx,
  927.     dbp->dup_compare == NULL ? __bam_defcmp : dbp->dup_compare,
  928.     &cmp)) != 0)
  929. return (ret);
  930. if (cmp <= 0)
  931. return (DB_NOTFOUND);
  932. /* Discard the current page, we're going to do a full search. */
  933. if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
  934. return (ret);
  935. cp->page = NULL;
  936. return (__bam_c_search(dbc, data, DB_GET_BOTH, &exact));
  937. }
  938. /*
  939.  * We're doing a DBC->c_get(DB_GET_BOTHC) and we're already searching
  940.  * a set of on-page duplicates (either sorted or unsorted).  Continue
  941.  * a linear search from after the current position.
  942.  *
  943.  * (Note that we could have just finished a "set" of one duplicate,
  944.  * i.e. not a duplicate at all, but the following check will always
  945.  * return DB_NOTFOUND in this case, which is the desired behavior.)
  946.  */
  947. if (cp->indx + P_INDX >= NUM_ENT(cp->page) ||
  948.     !IS_DUPLICATE(dbc, cp->indx, cp->indx + P_INDX))
  949. return (DB_NOTFOUND);
  950. cp->indx += P_INDX;
  951. return (__bam_getboth_finddatum(dbc, data));
  952. }
  953. /*
  954.  * __bam_getboth_finddatum --
  955.  * Find a matching on-page data item.
  956.  */
  957. static int
  958. __bam_getboth_finddatum(dbc, data)
  959. DBC *dbc;
  960. DBT *data;
  961. {
  962. BTREE_CURSOR *cp;
  963. DB *dbp;
  964. db_indx_t base, lim, top;
  965. int cmp, ret;
  966. dbp = dbc->dbp;
  967. cp = (BTREE_CURSOR *)dbc->internal;
  968. /*
  969.  * Called (sometimes indirectly) from DBC->get to search on-page data
  970.  * item(s) for a matching value.  If the original flag was DB_GET_BOTH,
  971.  * the cursor argument is set to the first data item for the key.  If
  972.  * the original flag was DB_GET_BOTHC, the cursor argument is set to
  973.  * the first data item that we can potentially return.  In both cases,
  974.  * there may or may not be additional duplicate data items to search.
  975.  *
  976.  * If the duplicates are not sorted, do a linear search.
  977.  *
  978.  * If the duplicates are sorted, do a binary search.  The reason for
  979.  * this is that large pages and small key/data pairs result in large
  980.  * numbers of on-page duplicates before they get pushed off-page.
  981.  */
  982. if (dbp->dup_compare == NULL) {
  983. for (;; cp->indx += P_INDX) {
  984. if (!IS_CUR_DELETED(dbc) &&
  985.     (ret = __bam_cmp(dbp, data, cp->page,
  986.     cp->indx + O_INDX, __bam_defcmp, &cmp)) != 0)
  987. return (ret);
  988. if (cmp == 0)
  989. return (0);
  990. if (cp->indx + P_INDX >= NUM_ENT(cp->page) ||
  991.     !IS_DUPLICATE(dbc, cp->indx, cp->indx + P_INDX))
  992. break;
  993. }
  994. } else {
  995. /*
  996.  * Find the top and bottom of the duplicate set.  Binary search
  997.  * requires at least two items, don't loop if there's only one.
  998.  */
  999. for (base = top = cp->indx;
  1000.     top < NUM_ENT(cp->page); top += P_INDX)
  1001. if (!IS_DUPLICATE(dbc, cp->indx, top))
  1002. break;
  1003. if (base == (top - P_INDX)) {
  1004. if  ((ret = __bam_cmp(dbp, data,
  1005.     cp->page, cp->indx + O_INDX,
  1006.     dbp->dup_compare, &cmp)) != 0)
  1007.        return (ret);
  1008. return (cmp == 0 ? 0 : DB_NOTFOUND);
  1009. }
  1010. for (lim =
  1011.     (top - base) / (db_indx_t)P_INDX; lim != 0; lim >>= 1) {
  1012. cp->indx = base + ((lim >> 1) * P_INDX);
  1013. if ((ret = __bam_cmp(dbp, data, cp->page,
  1014.     cp->indx + O_INDX, dbp->dup_compare, &cmp)) != 0)
  1015. return (ret);
  1016. if (cmp == 0) {
  1017. if (!IS_CUR_DELETED(dbc))
  1018. return (0);
  1019. break;
  1020. }
  1021. if (cmp > 0) {
  1022. base = cp->indx + P_INDX;
  1023. --lim;
  1024. }
  1025. }
  1026. }
  1027. return (DB_NOTFOUND);
  1028. }
  1029. /*
  1030.  * __bam_c_put --
  1031.  * Put using a cursor.
  1032.  */
  1033. static int
  1034. __bam_c_put(dbc, key, data, flags, pgnop)
  1035. DBC *dbc;
  1036. DBT *key, *data;
  1037. u_int32_t flags;
  1038. db_pgno_t *pgnop;
  1039. {
  1040. BTREE_CURSOR *cp;
  1041. DB *dbp;
  1042. DBT dbt;
  1043. u_int32_t iiop;
  1044. int cmp, exact, needkey, ret, stack;
  1045. void *arg;
  1046. dbp = dbc->dbp;
  1047. cp = (BTREE_CURSOR *)dbc->internal;
  1048. split: needkey = ret = stack = 0;
  1049. switch (flags) {
  1050. case DB_AFTER:
  1051. case DB_BEFORE:
  1052. case DB_CURRENT:
  1053. needkey = 1;
  1054. iiop = flags;
  1055. /*
  1056.  * If the Btree has record numbers (and we're not replacing an
  1057.  * existing record), we need a complete stack so that we can
  1058.  * adjust the record counts.  The check for flags == DB_CURRENT
  1059.  * is superfluous but left in for clarity.  (If C_RECNUM is set
  1060.  * we know that flags must be DB_CURRENT, as DB_AFTER/DB_BEFORE
  1061.  * are illegal in a Btree unless it's configured for duplicates
  1062.  * and you cannot configure a Btree for both record renumbering
  1063.  * and duplicates.)
  1064.  */
  1065. if (flags == DB_CURRENT &&
  1066.     F_ISSET(cp, C_RECNUM) && F_ISSET(cp, C_DELETED)) {
  1067. if ((ret = __bam_c_getstack(dbc)) != 0)
  1068. goto err;
  1069. /*
  1070.  * Initialize the cursor from the stack.  Don't take
  1071.  * the page number or page index, they should already
  1072.  * be set.
  1073.  */
  1074. cp->page = cp->csp->page;
  1075. cp->lock = cp->csp->lock;
  1076. cp->lock_mode = cp->csp->lock_mode;
  1077. stack = 1;
  1078. break;
  1079. }
  1080. /* Acquire the current page with a write lock. */
  1081. ACQUIRE_WRITE_LOCK(dbc, ret);
  1082. if (ret != 0)
  1083. goto err;
  1084. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
  1085. goto err;
  1086. break;
  1087. case DB_KEYFIRST:
  1088. case DB_KEYLAST:
  1089. case DB_NODUPDATA:
  1090. /*
  1091.  * Searching off-page, sorted duplicate tree: do a tree search
  1092.  * for the correct item; __bam_c_search returns the smallest
  1093.  * slot greater than the key, use it.
  1094.  */
  1095. if (F_ISSET(dbc, DBC_OPD)) {
  1096. if ((ret =
  1097.     __bam_c_search(dbc, data, flags, &exact)) != 0)
  1098. goto err;
  1099. stack = 1;
  1100. /* Disallow "sorted" duplicate duplicates. */
  1101. if (exact) {
  1102. ret = __db_duperr(dbp, flags);
  1103. goto err;
  1104. }
  1105. iiop = DB_BEFORE;
  1106. break;
  1107. }
  1108. /* Searching a btree. */
  1109. if ((ret = __bam_c_search(dbc, key,
  1110.     flags == DB_KEYFIRST || dbp->dup_compare != NULL ?
  1111.     DB_KEYFIRST : DB_KEYLAST, &exact)) != 0)
  1112. goto err;
  1113. stack = 1;
  1114. /*
  1115.  * If we don't have an exact match, __bam_c_search returned
  1116.  * the smallest slot greater than the key, use it.
  1117.  */
  1118. if (!exact) {
  1119. iiop = DB_KEYFIRST;
  1120. break;
  1121. }
  1122. /*
  1123.  * If duplicates aren't supported, replace the current item.
  1124.  * (If implementing the DB->put function, our caller already
  1125.  * checked the DB_NOOVERWRITE flag.)
  1126.  */
  1127. if (!F_ISSET(dbp, DB_AM_DUP)) {
  1128. iiop = DB_CURRENT;
  1129. break;
  1130. }
  1131. /*
  1132.  * If we find a matching entry, it may be an off-page duplicate
  1133.  * tree.  Return the page number to our caller, we need a new
  1134.  * cursor.
  1135.  */
  1136. if (pgnop != NULL && __bam_isopd(dbc, pgnop))
  1137. goto done;
  1138. /* If the duplicates aren't sorted, move to the right slot. */
  1139. if (dbp->dup_compare == NULL) {
  1140. if (flags == DB_KEYFIRST)
  1141. iiop = DB_BEFORE;
  1142. else
  1143. for (;; cp->indx += P_INDX)
  1144. if (cp->indx + P_INDX >=
  1145.     NUM_ENT(cp->page) ||
  1146.     !IS_DUPLICATE(dbc, cp->indx,
  1147.     cp->indx + P_INDX)) {
  1148. iiop = DB_AFTER;
  1149. break;
  1150. }
  1151. break;
  1152. }
  1153. /*
  1154.  * We know that we're looking at the first of a set of sorted
  1155.  * on-page duplicates.  Walk the list to find the right slot.
  1156.  */
  1157. for (;; cp->indx += P_INDX) {
  1158. if ((ret = __bam_cmp(dbp, data, cp->page,
  1159.     cp->indx + O_INDX, dbp->dup_compare, &cmp)) !=0)
  1160. return (ret);
  1161. if (cmp < 0) {
  1162. iiop = DB_BEFORE;
  1163. break;
  1164. }
  1165. /* Disallow "sorted" duplicate duplicates. */
  1166. if (cmp == 0) {
  1167. if (IS_DELETED(cp->page, cp->indx)) {
  1168. iiop = DB_CURRENT;
  1169. break;
  1170. }
  1171. ret = __db_duperr(dbp, flags);
  1172. goto err;
  1173. }
  1174. if (cp->indx + P_INDX >= NUM_ENT(cp->page) ||
  1175.     ((PAGE *)cp->page)->inp[cp->indx] !=
  1176.     ((PAGE *)cp->page)->inp[cp->indx + P_INDX]) {
  1177. iiop = DB_AFTER;
  1178. break;
  1179. }
  1180. }
  1181. break;
  1182. default:
  1183. ret = __db_unknown_flag(dbp->dbenv, "__bam_c_put", flags);
  1184. goto err;
  1185. }
  1186. switch (ret = __bam_iitem(dbc, key, data, iiop, 0)) {
  1187. case 0:
  1188. break;
  1189. case DB_NEEDSPLIT:
  1190. /*
  1191.  * To split, we need a key for the page.  Either use the key
  1192.  * argument or get a copy of the key from the page.
  1193.  */
  1194. if (flags == DB_AFTER ||
  1195.     flags == DB_BEFORE || flags == DB_CURRENT) {
  1196. memset(&dbt, 0, sizeof(DBT));
  1197. if ((ret = __db_ret(dbp, cp->page, 0, &dbt,
  1198.     &dbc->rkey.data, &dbc->rkey.ulen)) != 0)
  1199. goto err;
  1200. arg = &dbt;
  1201. } else
  1202. arg = F_ISSET(dbc, DBC_OPD) ? data : key;
  1203. /*
  1204.  * Discard any locks and pinned pages (the locks are discarded
  1205.  * even if we're running with transactions, as they lock pages
  1206.  * that we're sorry we ever acquired).  If stack is set and the
  1207.  * cursor entries are valid, they point to the same entries as
  1208.  * the stack, don't free them twice.
  1209.  */
  1210. if (stack)
  1211. ret = __bam_stkrel(dbc, STK_CLRDBC | STK_NOLOCK);
  1212. else
  1213. DISCARD_CUR(dbc, ret);
  1214. if (ret != 0)
  1215. goto err;
  1216. /* Split the tree. */
  1217. if ((ret = __bam_split(dbc, arg)) != 0)
  1218. return (ret);
  1219. goto split;
  1220. default:
  1221. goto err;
  1222. }
  1223. err:
  1224. done: /*
  1225.  * Discard any pages pinned in the tree and their locks, except for
  1226.  * the leaf page.  Note, the leaf page participated in any stack we
  1227.  * acquired, and so we have to adjust the stack as necessary.  If
  1228.  * there was only a single page on the stack, we don't have to free
  1229.  * further stack pages.
  1230.  */
  1231. if (stack && BT_STK_POP(cp) != NULL)
  1232. (void)__bam_stkrel(dbc, 0);
  1233. /*
  1234.  * Regardless of whether we were successful or not, clear the delete
  1235.  * flag.  If we're successful, we either moved the cursor or the item
  1236.  * is no longer deleted.  If we're not successful, then we're just a
  1237.  * copy, no need to have the flag set.
  1238.  */
  1239. F_CLR(cp, C_DELETED);
  1240. return (ret);
  1241. }
  1242. /*
  1243.  * __bam_c_rget --
  1244.  * Return the record number for a cursor.
  1245.  *
  1246.  * PUBLIC: int __bam_c_rget __P((DBC *, DBT *, u_int32_t));
  1247.  */
  1248. int
  1249. __bam_c_rget(dbc, data, flags)
  1250. DBC *dbc;
  1251. DBT *data;
  1252. u_int32_t flags;
  1253. {
  1254. BTREE_CURSOR *cp;
  1255. DB *dbp;
  1256. DBT dbt;
  1257. db_recno_t recno;
  1258. int exact, ret;
  1259. COMPQUIET(flags, 0);
  1260. dbp = dbc->dbp;
  1261. cp = (BTREE_CURSOR *)dbc->internal;
  1262. /*
  1263.  * Get the page with the current item on it.
  1264.  * Get a copy of the key.
  1265.  * Release the page, making sure we don't release it twice.
  1266.  */
  1267. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &cp->page)) != 0)
  1268. return (ret);
  1269. memset(&dbt, 0, sizeof(DBT));
  1270. if ((ret = __db_ret(dbp, cp->page,
  1271.     cp->indx, &dbt, &dbc->rkey.data, &dbc->rkey.ulen)) != 0)
  1272. goto err;
  1273. ret = memp_fput(dbp->mpf, cp->page, 0);
  1274. cp->page = NULL;
  1275. if (ret != 0)
  1276. return (ret);
  1277. if ((ret = __bam_search(dbc, &dbt,
  1278.     F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND,
  1279.     1, &recno, &exact)) != 0)
  1280. goto err;
  1281. ret = __db_retcopy(dbp, data,
  1282.     &recno, sizeof(recno), &dbc->rdata.data, &dbc->rdata.ulen);
  1283. /* Release the stack. */
  1284. err: __bam_stkrel(dbc, 0);
  1285. return (ret);
  1286. }
  1287. /*
  1288.  * __bam_c_writelock --
  1289.  * Upgrade the cursor to a write lock.
  1290.  */
  1291. static int
  1292. __bam_c_writelock(dbc)
  1293. DBC *dbc;
  1294. {
  1295. BTREE_CURSOR *cp;
  1296. int ret;
  1297. cp = (BTREE_CURSOR *)dbc->internal;
  1298. if (cp->lock_mode == DB_LOCK_WRITE)
  1299. return (0);
  1300. /*
  1301.  * When writing to an off-page duplicate tree, we need to have the
  1302.  * appropriate page in the primary tree locked.  The general DBC
  1303.  * code calls us first with the primary cursor so we can acquire the
  1304.  * appropriate lock.
  1305.  */
  1306. ACQUIRE_WRITE_LOCK(dbc, ret);
  1307. return (ret);
  1308. }
  1309. /*
  1310.  * __bam_c_first --
  1311.  * Return the first record.
  1312.  */
  1313. static int
  1314. __bam_c_first(dbc)
  1315. DBC *dbc;
  1316. {
  1317. BTREE_CURSOR *cp;
  1318. DB *dbp;
  1319. db_pgno_t pgno;
  1320. int ret;
  1321. dbp = dbc->dbp;
  1322. cp = (BTREE_CURSOR *)dbc->internal;
  1323. ret = 0;
  1324. /* Walk down the left-hand side of the tree. */
  1325. for (pgno = cp->root;;) {
  1326. ACQUIRE_CUR_SET(dbc, DB_LOCK_READ, pgno, ret);
  1327. if (ret != 0)
  1328. return (ret);
  1329. /* If we find a leaf page, we're done. */
  1330. if (ISLEAF(cp->page))
  1331. break;
  1332. pgno = GET_BINTERNAL(cp->page, 0)->pgno;
  1333. }
  1334. /* If we want a write lock instead of a read lock, get it now. */
  1335. if (F_ISSET(dbc, DBC_RMW)) {
  1336. ACQUIRE_WRITE_LOCK(dbc, ret);
  1337. if (ret != 0)
  1338. return (ret);
  1339. }
  1340. /* If on an empty page or a deleted record, move to the next one. */
  1341. if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(dbc))
  1342. if ((ret = __bam_c_next(dbc, 0)) != 0)
  1343. return (ret);
  1344. return (0);
  1345. }
  1346. /*
  1347.  * __bam_c_last --
  1348.  * Return the last record.
  1349.  */
  1350. static int
  1351. __bam_c_last(dbc)
  1352. DBC *dbc;
  1353. {
  1354. BTREE_CURSOR *cp;
  1355. DB *dbp;
  1356. db_pgno_t pgno;
  1357. int ret;
  1358. dbp = dbc->dbp;
  1359. cp = (BTREE_CURSOR *)dbc->internal;
  1360. ret = 0;
  1361. /* Walk down the right-hand side of the tree. */
  1362. for (pgno = cp->root;;) {
  1363. ACQUIRE_CUR_SET(dbc, DB_LOCK_READ, pgno, ret);
  1364. if (ret != 0)
  1365. return (ret);
  1366. /* If we find a leaf page, we're done. */
  1367. if (ISLEAF(cp->page))
  1368. break;
  1369. pgno =
  1370.     GET_BINTERNAL(cp->page, NUM_ENT(cp->page) - O_INDX)->pgno;
  1371. }
  1372. /* If we want a write lock instead of a read lock, get it now. */
  1373. if (F_ISSET(dbc, DBC_RMW)) {
  1374. ACQUIRE_WRITE_LOCK(dbc, ret);
  1375. if (ret != 0)
  1376. return (ret);
  1377. }
  1378. cp->indx = NUM_ENT(cp->page) == 0 ? 0 :
  1379.     NUM_ENT(cp->page) -
  1380.     (TYPE(cp->page) == P_LBTREE ? P_INDX : O_INDX);
  1381. /* If on an empty page or a deleted record, move to the previous one. */
  1382. if (NUM_ENT(cp->page) == 0 || IS_CUR_DELETED(dbc))
  1383. if ((ret = __bam_c_prev(dbc)) != 0)
  1384. return (ret);
  1385. return (0);
  1386. }
  1387. /*
  1388.  * __bam_c_next --
  1389.  * Move to the next record.
  1390.  */
  1391. static int
  1392. __bam_c_next(dbc, initial_move)
  1393. DBC *dbc;
  1394. int initial_move;
  1395. {
  1396. BTREE_CURSOR *cp;
  1397. DB *dbp;
  1398. db_indx_t adjust;
  1399. db_lockmode_t lock_mode;
  1400. db_pgno_t pgno;
  1401. int ret;
  1402. dbp = dbc->dbp;
  1403. cp = (BTREE_CURSOR *)dbc->internal;
  1404. ret = 0;
  1405. /*
  1406.  * We're either moving through a page of duplicates or a btree leaf
  1407.  * page.
  1408.  *
  1409.  * !!!
  1410.  * This code handles empty pages and pages with only deleted entries.
  1411.  */
  1412. if (F_ISSET(dbc, DBC_OPD)) {
  1413. adjust = O_INDX;
  1414. lock_mode = DB_LOCK_NG;
  1415. } else {
  1416. adjust = dbc->dbtype == DB_BTREE ? P_INDX : O_INDX;
  1417. lock_mode =
  1418.     F_ISSET(dbc, DBC_RMW) ? DB_LOCK_WRITE : DB_LOCK_READ;
  1419. }
  1420. if (cp->page == NULL) {
  1421. ACQUIRE_CUR(dbc, lock_mode, ret);
  1422. if (ret != 0)
  1423. return (ret);
  1424. }
  1425. if (initial_move)
  1426. cp->indx += adjust;
  1427. for (;;) {
  1428. /*
  1429.  * If at the end of the page, move to a subsequent page.
  1430.  *
  1431.  * !!!
  1432.  * Check for >= NUM_ENT.  If the original search landed us on
  1433.  * NUM_ENT, we may have incremented indx before the test.
  1434.  */
  1435. if (cp->indx >= NUM_ENT(cp->page)) {
  1436. if ((pgno
  1437.     = NEXT_PGNO(cp->page)) == PGNO_INVALID)
  1438. return (DB_NOTFOUND);
  1439. ACQUIRE_CUR_SET(dbc, lock_mode, pgno, ret);
  1440. if (ret != 0)
  1441. return (ret);
  1442. continue;
  1443. }
  1444. if (IS_CUR_DELETED(dbc)) {
  1445. cp->indx += adjust;
  1446. continue;
  1447. }
  1448. break;
  1449. }
  1450. return (0);
  1451. }
  1452. /*
  1453.  * __bam_c_prev --
  1454.  * Move to the previous record.
  1455.  */
  1456. static int
  1457. __bam_c_prev(dbc)
  1458. DBC *dbc;
  1459. {
  1460. BTREE_CURSOR *cp;
  1461. DB *dbp;
  1462. db_indx_t adjust;
  1463. db_lockmode_t lock_mode;
  1464. db_pgno_t pgno;
  1465. int ret;
  1466. dbp = dbc->dbp;
  1467. cp = (BTREE_CURSOR *)dbc->internal;
  1468. ret = 0;
  1469. /*
  1470.  * We're either moving through a page of duplicates or a btree leaf
  1471.  * page.
  1472.  *
  1473.  * !!!
  1474.  * This code handles empty pages and pages with only deleted entries.
  1475.  */
  1476. if (F_ISSET(dbc, DBC_OPD)) {
  1477. adjust = O_INDX;
  1478. lock_mode = DB_LOCK_NG;
  1479. } else {
  1480. adjust = dbc->dbtype == DB_BTREE ? P_INDX : O_INDX;
  1481. lock_mode =
  1482.     F_ISSET(dbc, DBC_RMW) ? DB_LOCK_WRITE : DB_LOCK_READ;
  1483. }
  1484. if (cp->page == NULL) {
  1485. ACQUIRE_CUR(dbc, lock_mode, ret);
  1486. if (ret != 0)
  1487. return (ret);
  1488. }
  1489. for (;;) {
  1490. /* If at the beginning of the page, move to a previous one. */
  1491. if (cp->indx == 0) {
  1492. if ((pgno =
  1493.     PREV_PGNO(cp->page)) == PGNO_INVALID)
  1494. return (DB_NOTFOUND);
  1495. ACQUIRE_CUR_SET(dbc, lock_mode, pgno, ret);
  1496. if (ret != 0)
  1497. return (ret);
  1498. if ((cp->indx = NUM_ENT(cp->page)) == 0)
  1499. continue;
  1500. }
  1501. /* Ignore deleted records. */
  1502. cp->indx -= adjust;
  1503. if (IS_CUR_DELETED(dbc))
  1504. continue;
  1505. break;
  1506. }
  1507. return (0);
  1508. }
  1509. /*
  1510.  * __bam_c_search --
  1511.  * Move to a specified record.
  1512.  */
  1513. static int
  1514. __bam_c_search(dbc, key, flags, exactp)
  1515. DBC *dbc;
  1516. const DBT *key;
  1517. u_int32_t flags;
  1518. int *exactp;
  1519. {
  1520. BTREE *t;
  1521. BTREE_CURSOR *cp;
  1522. DB *dbp;
  1523. PAGE *h;
  1524. db_indx_t indx;
  1525. db_pgno_t bt_lpgno;
  1526. db_recno_t recno;
  1527. u_int32_t sflags;
  1528. int cmp, ret;
  1529. dbp = dbc->dbp;
  1530. cp = (BTREE_CURSOR *)dbc->internal;
  1531. t = dbp->bt_internal;
  1532. ret = 0;
  1533. /*
  1534.  * Find an entry in the database.  Discard any lock we currently hold,
  1535.  * we're going to search the tree.
  1536.  */
  1537. DISCARD_CUR(dbc, ret);
  1538. if (ret != 0)
  1539. return (ret);
  1540. switch (flags) {
  1541. case DB_SET_RECNO:
  1542. if ((ret = __ram_getno(dbc, key, &recno, 0)) != 0)
  1543. return (ret);
  1544. sflags = (F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND) | S_EXACT;
  1545. if ((ret = __bam_rsearch(dbc, &recno, sflags, 1, exactp)) != 0)
  1546. return (ret);
  1547. break;
  1548. case DB_SET:
  1549. case DB_GET_BOTH:
  1550. sflags = (F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND) | S_EXACT;
  1551. goto search;
  1552. case DB_SET_RANGE:
  1553. sflags =
  1554.     (F_ISSET(dbc, DBC_RMW) ? S_WRITE : S_READ) | S_DUPFIRST;
  1555. goto search;
  1556. case DB_KEYFIRST:
  1557. sflags = S_KEYFIRST;
  1558. goto fast_search;
  1559. case DB_KEYLAST:
  1560. case DB_NODUPDATA:
  1561. sflags = S_KEYLAST;
  1562. fast_search: /*
  1563.  * If the application has a history of inserting into the first
  1564.  * or last pages of the database, we check those pages first to
  1565.  * avoid doing a full search.
  1566.  *
  1567.  * If the tree has record numbers, we need a complete stack so
  1568.  * that we can adjust the record counts, so fast_search isn't
  1569.  * possible.
  1570.  */
  1571. if (F_ISSET(cp, C_RECNUM))
  1572. goto search;
  1573. /*
  1574.  * !!!
  1575.  * We do not mutex protect the t->bt_lpgno field, which means
  1576.  * that it can only be used in an advisory manner.  If we find
  1577.  * page we can use, great.  If we don't, we don't care, we do
  1578.  * it the slow way instead.  Regardless, copy it into a local
  1579.  * variable, otherwise we might acquire a lock for a page and
  1580.  * then read a different page because it changed underfoot.
  1581.  */
  1582. bt_lpgno = t->bt_lpgno;
  1583. /*
  1584.  * If the tree has no history of insertion, do it the slow way.
  1585.  */
  1586. if (bt_lpgno == PGNO_INVALID)
  1587. goto search;
  1588. /* Lock and retrieve the page on which we last inserted. */
  1589. h = NULL;
  1590. ACQUIRE(dbc,
  1591.     DB_LOCK_WRITE, bt_lpgno, cp->lock, bt_lpgno, h, ret);
  1592. if (ret != 0)
  1593. goto fast_miss;
  1594. /*
  1595.  * It's okay if the page type isn't right or it's empty, it
  1596.  * just means that the world changed.
  1597.  */
  1598. if (TYPE(h) != P_LBTREE || NUM_ENT(h) == 0)
  1599. goto fast_miss;
  1600. /*
  1601.  * What we do here is test to see if we're at the beginning or
  1602.  * end of the tree and if the new item sorts before/after the
  1603.  * first/last page entry.  We don't try and catch inserts into
  1604.  * the middle of the tree (although we could, as long as there
  1605.  * were two keys on the page and we saved both the index and
  1606.  * the page number of the last insert).
  1607.  */
  1608. if (h->next_pgno == PGNO_INVALID) {
  1609. indx = NUM_ENT(h) - P_INDX;
  1610. if ((ret = __bam_cmp(dbp,
  1611.     key, h, indx, t->bt_compare, &cmp)) != 0)
  1612. return (ret);
  1613. if (cmp < 0)
  1614. goto try_begin;
  1615. if (cmp > 0) {
  1616. indx += P_INDX;
  1617. goto fast_hit;
  1618. }
  1619. /*
  1620.  * Found a duplicate.  If doing DB_KEYLAST, we're at
  1621.  * the correct position, otherwise, move to the first
  1622.  * of the duplicates.  If we're looking at off-page
  1623.  * duplicates, duplicate duplicates aren't permitted,
  1624.  * so we're done.
  1625.  */
  1626. if (flags == DB_KEYLAST)
  1627. goto fast_hit;
  1628. for (;
  1629.     indx > 0 && h->inp[indx - P_INDX] == h->inp[indx];
  1630.     indx -= P_INDX)
  1631. ;
  1632. goto fast_hit;
  1633. }
  1634. try_begin: if (h->prev_pgno == PGNO_INVALID) {
  1635. indx = 0;
  1636. if ((ret = __bam_cmp(dbp,
  1637.     key, h, indx, t->bt_compare, &cmp)) != 0)
  1638. return (ret);
  1639. if (cmp > 0)
  1640. goto fast_miss;
  1641. if (cmp < 0)
  1642. goto fast_hit;
  1643. /*
  1644.  * Found a duplicate.  If doing DB_KEYFIRST, we're at
  1645.  * the correct position, otherwise, move to the last
  1646.  * of the duplicates.  If we're looking at off-page
  1647.  * duplicates, duplicate duplicates aren't permitted,
  1648.  * so we're done.
  1649.  */
  1650. if (flags == DB_KEYFIRST)
  1651. goto fast_hit;
  1652. for (;
  1653.     indx < (db_indx_t)(NUM_ENT(h) - P_INDX) &&
  1654.     h->inp[indx] == h->inp[indx + P_INDX];
  1655.     indx += P_INDX)
  1656. ;
  1657. goto fast_hit;
  1658. }
  1659. goto fast_miss;
  1660. fast_hit: /* Set the exact match flag, we may have found a duplicate. */
  1661. *exactp = cmp == 0;
  1662. /*
  1663.  * Insert the entry in the stack.  (Our caller is likely to
  1664.  * call __bam_stkrel() after our return.)
  1665.  */
  1666. BT_STK_CLR(cp);
  1667. BT_STK_ENTER(dbp->dbenv,
  1668.     cp, h, indx, cp->lock, cp->lock_mode, ret);
  1669. if (ret != 0)
  1670. return (ret);
  1671. break;
  1672. fast_miss: /*
  1673.  * This was not the right page, so we do not need to retain
  1674.  * the lock even in the presence of transactions.
  1675.  */
  1676. DISCARD(dbc, 1, cp->lock, h, ret);
  1677. if (ret != 0)
  1678. return (ret);
  1679. search: if ((ret =
  1680.     __bam_search(dbc, key, sflags, 1, NULL, exactp)) != 0)
  1681. return (ret);
  1682. break;
  1683. default:
  1684. return (__db_unknown_flag(dbp->dbenv, "__bam_c_search", flags));
  1685. }
  1686. /* Initialize the cursor from the stack. */
  1687. cp->page = cp->csp->page;
  1688. cp->pgno = cp->csp->page->pgno;
  1689. cp->indx = cp->csp->indx;
  1690. cp->lock = cp->csp->lock;
  1691. cp->lock_mode = cp->csp->lock_mode;
  1692. /*
  1693.  * If we inserted a key into the first or last slot of the tree,
  1694.  * remember where it was so we can do it more quickly next time.
  1695.  */
  1696. if (TYPE(cp->page) == P_LBTREE &&
  1697.     (flags == DB_KEYFIRST || flags == DB_KEYLAST))
  1698. t->bt_lpgno =
  1699.     (NEXT_PGNO(cp->page) == PGNO_INVALID &&
  1700.     cp->indx >= NUM_ENT(cp->page)) ||
  1701.     (PREV_PGNO(cp->page) == PGNO_INVALID &&
  1702.     cp->indx == 0) ? cp->pgno : PGNO_INVALID;
  1703. return (0);
  1704. }
  1705. /*
  1706.  * __bam_c_physdel --
  1707.  * Physically remove an item from the page.
  1708.  */
  1709. static int
  1710. __bam_c_physdel(dbc)
  1711. DBC *dbc;
  1712. {
  1713. BTREE_CURSOR *cp;
  1714. DB *dbp;
  1715. DBT key;
  1716. DB_LOCK lock;
  1717. PAGE *h;
  1718. db_pgno_t pgno;
  1719. int delete_page, empty_page, exact, level, ret;
  1720. dbp = dbc->dbp;
  1721. cp = (BTREE_CURSOR *)dbc->internal;
  1722. delete_page = empty_page = ret = 0;
  1723. /* If the page is going to be emptied, consider deleting it. */
  1724. delete_page = empty_page =
  1725.     NUM_ENT(cp->page) == (TYPE(cp->page) == P_LBTREE ? 2 : 1);
  1726. /*
  1727.  * Check if the application turned off reverse splits.  Applications
  1728.  * can't turn off reverse splits in off-page duplicate trees, that
  1729.  * space will never be reused unless the exact same key is specified.
  1730.  */
  1731. if (delete_page &&
  1732.     !F_ISSET(dbc, DBC_OPD) && F_ISSET(dbp, DB_BT_REVSPLIT))
  1733. delete_page = 0;
  1734. /*
  1735.  * We never delete the last leaf page.  (Not really true -- we delete
  1736.  * the last leaf page of off-page duplicate trees, but that's handled
  1737.  * by our caller, not down here.)
  1738.  */
  1739. if (delete_page && cp->pgno == cp->root)
  1740. delete_page = 0;
  1741. /*
  1742.  * To delete a leaf page other than an empty root page, we need a
  1743.  * copy of a key from the page.  Use the 0th page index since it's
  1744.  * the last key the page held.
  1745.  */
  1746. if (delete_page) {
  1747. memset(&key, 0, sizeof(DBT));
  1748. if ((ret = __db_ret(dbp, cp->page,
  1749.     0, &key, &dbc->rkey.data, &dbc->rkey.ulen)) != 0)
  1750. return (ret);
  1751. }
  1752. /*
  1753.  * Delete the items.  If page isn't empty, we adjust the cursors.
  1754.  *
  1755.  * !!!
  1756.  * The following operations to delete a page may deadlock.  The easy
  1757.  * scenario is if we're deleting an item because we're closing cursors
  1758.  * because we've already deadlocked and want to call txn_abort().  If
  1759.  * we fail due to deadlock, we'll leave a locked, possibly empty page
  1760.  * in the tree, which won't be empty long because we'll undo the delete
  1761.  * when we undo the transaction's modifications.
  1762.  *
  1763.  * !!!
  1764.  * Delete the key item first, otherwise the on-page duplicate checks
  1765.  * in __bam_ditem() won't work!
  1766.  */
  1767. if (TYPE(cp->page) == P_LBTREE) {
  1768. if ((ret = __bam_ditem(dbc, cp->page, cp->indx)) != 0)
  1769. return (ret);
  1770. if (!empty_page)
  1771. if ((ret = __bam_ca_di(dbc,
  1772.     PGNO(cp->page), cp->indx, -1)) != 0)
  1773. return (ret);
  1774. }
  1775. if ((ret = __bam_ditem(dbc, cp->page, cp->indx)) != 0)
  1776. return (ret);
  1777. if (!empty_page)
  1778. if ((ret = __bam_ca_di(dbc, PGNO(cp->page), cp->indx, -1)) != 0)
  1779. return (ret);
  1780. /* If we're not going to try and delete the page, we're done. */
  1781. if (!delete_page)
  1782. return (0);
  1783. /*
  1784.  * Call __bam_search to reacquire the empty leaf page, but this time
  1785.  * get both the leaf page and it's parent, locked.  Jump back up the
  1786.  * tree, until we have the top pair of pages that we want to delete.
  1787.  * Once we have the top page that we want to delete locked, lock the
  1788.  * underlying pages and check to make sure they're still empty.  If
  1789.  * they are, delete them.
  1790.  */
  1791. for (level = LEAFLEVEL;; ++level) {
  1792. /* Acquire a page and its parent, locked. */
  1793. if ((ret = __bam_search(
  1794.     dbc, &key, S_WRPAIR, level, NULL, &exact)) != 0)
  1795. return (ret);
  1796. /*
  1797.  * If we reach the root or the parent page isn't going to be
  1798.  * empty when we delete one record, stop.
  1799.  */
  1800. h = cp->csp[-1].page;
  1801. if (h->pgno == cp->root || NUM_ENT(h) != 1)
  1802. break;
  1803. /* Discard the stack, retaining no locks. */
  1804. (void)__bam_stkrel(dbc, STK_NOLOCK);
  1805. }
  1806. /*
  1807.  * Move the stack pointer one after the last entry, we may be about
  1808.  * to push more items onto the page stack.
  1809.  */
  1810. ++cp->csp;
  1811. /*
  1812.  * cp->csp[-2].page is now the parent page, which we may or may not be
  1813.  * going to delete, and cp->csp[-1].page is the first page we know we
  1814.  * are going to delete.  Walk down the chain of pages, acquiring pages
  1815.  * until we've acquired a leaf page.  Generally, this shouldn't happen;
  1816.  * we should only see a single internal page with one item and a single
  1817.  * leaf page with no items.  The scenario where we could see something
  1818.  * else is if reverse splits were turned off for awhile and then turned
  1819.  * back on.  That could result in all sorts of strangeness, e.g., empty
  1820.  * pages in the tree, trees that looked like linked lists, and so on.
  1821.  *
  1822.  * !!!
  1823.  * Sheer paranoia: if we find any pages that aren't going to be emptied
  1824.  * by the delete, someone else added an item while we were walking the
  1825.  * tree, and we discontinue the delete.  Shouldn't be possible, but we
  1826.  * check regardless.
  1827.  */
  1828. for (h = cp->csp[-1].page;;) {
  1829. if (ISLEAF(h)) {
  1830. if (NUM_ENT(h) != 0)
  1831. break;
  1832. break;
  1833. } else
  1834. if (NUM_ENT(h) != 1)
  1835. break;
  1836. /*
  1837.  * Get the next page, write lock it and push it onto the stack.
  1838.  * We know it's index 0, because it can only have one element.
  1839.  */
  1840. switch (TYPE(h)) {
  1841. case P_IBTREE:
  1842. pgno = GET_BINTERNAL(h, 0)->pgno;
  1843. break;
  1844. case P_IRECNO:
  1845. pgno = GET_RINTERNAL(h, 0)->pgno;
  1846. break;
  1847. default:
  1848. return (__db_pgfmt(dbp, PGNO(h)));
  1849. }
  1850. if ((ret =
  1851.     __db_lget(dbc, 0, pgno, DB_LOCK_WRITE, 0, &lock)) != 0)
  1852. break;
  1853. if ((ret = memp_fget(dbp->mpf, &pgno, 0, &h)) != 0)
  1854. break;
  1855. BT_STK_PUSH(dbp->dbenv, cp, h, 0, lock, DB_LOCK_WRITE, ret);
  1856. if (ret != 0)
  1857. break;
  1858. }
  1859. /* Adjust the cursor stack to reference the last page on the stack. */
  1860. BT_STK_POP(cp);
  1861. /*
  1862.  * If everything worked, delete the stack, otherwise, release the
  1863.  * stack and page locks without further damage.
  1864.  */
  1865. if (ret == 0)
  1866. ret = __bam_dpages(dbc, cp->sp);
  1867. else
  1868. (void)__bam_stkrel(dbc, 0);
  1869. return (ret);
  1870. }
  1871. /*
  1872.  * __bam_c_getstack --
  1873.  * Acquire a full stack for a cursor.
  1874.  */
  1875. static int
  1876. __bam_c_getstack(dbc)
  1877. DBC *dbc;
  1878. {
  1879. BTREE_CURSOR *cp;
  1880. DB *dbp;
  1881. DBT dbt;
  1882. PAGE *h;
  1883. int exact, ret, t_ret;
  1884. dbp = dbc->dbp;
  1885. cp = (BTREE_CURSOR *)dbc->internal;
  1886. /*
  1887.  * Get the page with the current item on it.  The caller of this
  1888.  * routine has to already hold a read lock on the page, so there
  1889.  * is no additional lock to acquire.
  1890.  */
  1891. if ((ret = memp_fget(dbp->mpf, &cp->pgno, 0, &h)) != 0)
  1892. return (ret);
  1893. /* Get a copy of a key from the page. */
  1894. memset(&dbt, 0, sizeof(DBT));
  1895. if ((ret = __db_ret(dbp,
  1896.     h, 0, &dbt, &dbc->rkey.data, &dbc->rkey.ulen)) != 0)
  1897. goto err;
  1898. /* Get a write-locked stack for the page. */
  1899. exact = 0;
  1900. ret = __bam_search(dbc, &dbt, S_KEYFIRST, 1, NULL, &exact);
  1901. err: /* Discard the key and the page. */
  1902. if ((t_ret = memp_fput(dbp->mpf, h, 0)) != 0 && ret == 0)
  1903. ret = t_ret;
  1904. return (ret);
  1905. }
  1906. /*
  1907.  * __bam_isopd --
  1908.  * Return if the cursor references an off-page duplicate tree via its
  1909.  * page number.
  1910.  */
  1911. static int
  1912. __bam_isopd(dbc, pgnop)
  1913. DBC *dbc;
  1914. db_pgno_t *pgnop;
  1915. {
  1916. BOVERFLOW *bo;
  1917. if (TYPE(dbc->internal->page) != P_LBTREE)
  1918. return (0);
  1919. bo = GET_BOVERFLOW(dbc->internal->page, dbc->internal->indx + O_INDX);
  1920. if (B_TYPE(bo->type) == B_DUPLICATE) {
  1921. *pgnop = bo->pgno;
  1922. return (1);
  1923. }
  1924. return (0);
  1925. }