2 * See the file LICENSE for redistribution information.
4 * Copyright (c) 1996, 1997
5 * Sleepycat Software. All rights reserved.
11 static const char sccsid[] = "@(#)bt_cursor.c 10.27 (Sleepycat) 9/3/97";
14 #ifndef NO_SYSTEM_INCLUDES
15 #include <sys/types.h>
27 static int __bam_c_close __P((DBC *));
28 static int __bam_c_del __P((DBC *, int));
29 static int __bam_c_first __P((DB *, CURSOR *));
30 static int __bam_c_get __P((DBC *, DBT *, DBT *, int));
31 static int __bam_c_last __P((DB *, CURSOR *));
32 static int __bam_c_next __P((DB *, CURSOR *, int));
33 static int __bam_c_physdel __P((DB *, CURSOR *, PAGE *));
34 static int __bam_c_prev __P((DB *, CURSOR *));
35 static int __bam_c_put __P((DBC *, DBT *, DBT *, int));
36 static int __bam_c_rget __P((DB *, CURSOR *, DBT *, DBT *, int));
37 static int __bam_c_search __P((DB *, CURSOR *, const DBT *, u_int, int, int *));
39 /* Discard the current page/lock held by a cursor. */
41 #define DISCARD(dbp, cp) { \
42 (void)memp_fput(dbp->mpf, (cp)->page, 0); \
44 (void)__BT_TLPUT((dbp), (cp)->lock); \
45 (cp)->lock = LOCK_INVALID; \
50 * Interface to the cursor functions.
52 * PUBLIC: int __bam_cursor __P((DB *, DB_TXN *, DBC **));
55 __bam_cursor(dbp, txn, dbcp)
63 DEBUG_LWRITE(dbp, txn, "bam_cursor", NULL, NULL, 0);
65 if ((dbc = (DBC *)calloc(1, sizeof(DBC))) == NULL)
67 if ((cp = (CURSOR *)calloc(1, sizeof(CURSOR))) == NULL) {
73 cp->pgno = cp->dpgno = PGNO_INVALID;
74 cp->lock = LOCK_INVALID;
79 dbc->c_close = __bam_c_close;
80 dbc->c_del = __bam_c_del;
81 dbc->c_get = __bam_c_get;
82 dbc->c_put = __bam_c_put;
84 /* All cursor structures hang off the main DB structure. */
86 TAILQ_INSERT_HEAD(&dbp->curs_queue, dbc, links);
87 DB_THREAD_UNLOCK(dbp);
95 * Close a single cursor.
105 DEBUG_LWRITE(dbc->dbp, dbc->txn, "bam_c_close", NULL, NULL, 0);
107 GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
110 /* If a cursor key was deleted do the actual deletion. */
111 ret = F_ISSET(cp, C_DELETED) ? __bam_c_physdel(dbp, cp, NULL) : 0;
113 /* Discard any lock if we're not inside a transaction. */
114 if (dbp->txn == NULL && cp->lock != LOCK_INVALID)
115 (void)__BT_TLPUT(dbp, cp->lock);
117 /* Remove the cursor from the queue. */
119 TAILQ_REMOVE(&dbp->curs_queue, dbc, links);
120 DB_THREAD_UNLOCK(dbp);
122 /* Discard the structures. */
123 FREE(cp, sizeof(CURSOR));
124 FREE(dbc, sizeof(DBC));
132 * Delete using a cursor.
135 __bam_c_del(dbc, flags)
147 DEBUG_LWRITE(dbc->dbp, dbc->txn, "bam_c_del", NULL, NULL, flags);
151 /* Check for invalid flags. */
152 if ((ret = __db_cdelchk(dbc->dbp, flags,
153 F_ISSET(dbc->dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
156 /* If already deleted, return failure. */
157 if (F_ISSET(cp, C_DELETED | C_REPLACE))
158 return (DB_KEYEMPTY);
160 GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
163 * We don't physically delete the record until the cursor moves,
164 * so we have to have a long-lived write lock on the page instead
165 * of a long-lived read lock. Note, we have to have a read lock
166 * to even get here, so we simply discard it.
168 if (F_ISSET(dbp, DB_AM_LOCKING) && cp->mode != DB_LOCK_WRITE) {
169 if ((ret = __bam_lget(dbp,
170 0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
172 (void)__BT_TLPUT(dbp, cp->lock);
174 cp->mode = DB_LOCK_WRITE;
178 * Acquire the underlying page (which may be different from the above
179 * page because it may be a duplicate page), and set the on-page and
180 * in-cursor delete flags. We don't need to lock it as we've already
181 * write-locked the page leading to it.
183 if (cp->dpgno == PGNO_INVALID) {
191 if ((ret = __bam_pget(dbp, &h, &pgno, 0)) != 0)
194 /* Log the change. */
195 if (DB_LOGGING(dbp) &&
196 (ret = __bam_cdel_log(dbp->dbenv->lg_info, dbp->txn, &LSN(h),
197 0, dbp->log_fileid, PGNO(h), &LSN(h), indx)) != 0) {
198 (void)memp_fput(dbp->mpf, h, 0);
202 /* Set the intent-to-delete flag on the page and in all cursors. */
203 if (cp->dpgno == PGNO_INVALID)
204 B_DSET(GET_BKEYDATA(h, indx + O_INDX)->type);
206 B_DSET(GET_BKEYDATA(h, indx)->type);
207 (void)__bam_ca_delete(dbp, pgno, indx, NULL);
209 ret = memp_fput(dbp->mpf, h, DB_MPOOL_DIRTY);
217 * Retrieve a key/data pair from the tree.
219 * PUBLIC: int __bam_get __P((DB *, DB_TXN *, DBT *, DBT *, int));
222 __bam_get(argdbp, txn, key, data, flags)
232 DEBUG_LREAD(argdbp, txn, "bam_get", key, NULL, flags);
234 /* Check for invalid flags. */
235 if ((ret = __db_getchk(argdbp, key, data, flags)) != 0)
238 /* Build a cursor. */
239 memset(&cp, 0, sizeof(cp));
241 cp.pgno = cp.dpgno = PGNO_INVALID;
242 cp.lock = LOCK_INVALID;
244 memset(&dbc, 0, sizeof(dbc));
250 if ((ret = __bam_c_get(&dbc,
251 key, data, LF_ISSET(DB_SET_RECNO) ? DB_SET_RECNO : DB_SET)) != 0)
254 /* Discard any lock, the cursor didn't really exist. */
255 if (cp.lock != LOCK_INVALID)
256 (void)__BT_TLPUT(argdbp, cp.lock);
263 * Get using a cursor (btree).
266 __bam_c_get(dbc, key, data, flags)
277 DEBUG_LREAD(dbc->dbp, dbc->txn, "bam_c_get",
278 flags == DB_SET || flags == DB_SET_RANGE ? key : NULL,
283 /* Check for invalid flags. */
284 if ((ret = __db_cgetchk(dbc->dbp,
285 key, data, flags, cp->pgno != PGNO_INVALID)) != 0)
288 GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
292 * Break out the code to return a cursor's record number. It
293 * has nothing to do with the cursor get code except that it's
294 * been rammed into the interface.
296 if (LF_ISSET(DB_GET_RECNO)) {
297 ret = __bam_c_rget(dbp, cp, key, data, flags);
302 /* Initialize the cursor for a new retrieval. */
305 cp->lock = LOCK_INVALID;
309 /* It's not possible to return a deleted record. */
310 if (F_ISSET(cp, C_DELETED | C_REPLACE)) {
312 return (DB_KEYEMPTY);
315 /* Get the page with the current item on it. */
316 if ((ret = __bam_pget(dbp, &cp->page, &cp->pgno, 0)) != 0)
320 if (cp->pgno != PGNO_INVALID) {
321 if ((ret = __bam_c_next(dbp, cp, 1)) != 0)
327 if ((ret = __bam_c_first(dbp, cp)) != 0)
331 if (cp->pgno != PGNO_INVALID) {
332 if ((ret = __bam_c_prev(dbp, cp)) != 0)
338 if ((ret = __bam_c_last(dbp, cp)) != 0)
344 __bam_c_search(dbp, cp, key, S_FIND, 1, &exact)) != 0)
350 __bam_c_search(dbp, cp, key, S_FIND, 0, &exact)) != 0)
356 __bam_c_search(dbp, cp, key, S_FIND, 0, &exact)) != 0)
362 * Return the key if the user didn't give us one. If we've moved to
363 * a duplicate page, we may no longer have a pointer to the main page,
364 * so we have to go get it. We know that it's already read-locked,
365 * however, so we don't have to acquire a new lock.
367 if (flags != DB_SET) {
368 if (cp->dpgno != PGNO_INVALID) {
369 if ((ret = __bam_pget(dbp, &h, &cp->pgno, 0)) != 0)
374 h, cp->indx, key, &t->bt_rkey.data, &t->bt_rkey.ulen);
375 if (cp->dpgno != PGNO_INVALID)
376 (void)memp_fput(dbp->mpf, h, 0);
381 /* Return the data. */
382 if ((ret = __db_ret(dbp, cp->page,
383 cp->dpgno == PGNO_INVALID ? cp->indx + O_INDX : cp->dindx,
384 data, &t->bt_rdata.data, &t->bt_rdata.ulen)) != 0)
388 * If the previous cursor record has been deleted, delete it. The
389 * returned key isn't a deleted key, so clear the flag.
391 if (F_ISSET(©, C_DELETED) && __bam_c_physdel(dbp, ©, cp->page))
393 F_CLR(cp, C_DELETED | C_REPLACE);
395 /* Release the previous lock, if any. */
396 if (copy.lock != LOCK_INVALID)
397 (void)__BT_TLPUT(dbp, copy.lock);
399 /* Release the pinned page. */
400 ret = memp_fput(dbp->mpf, cp->page, 0);
405 err: if (cp->page != NULL)
406 (void)memp_fput(dbp->mpf, cp->page, 0);
407 if (cp->lock != LOCK_INVALID)
408 (void)__BT_TLPUT(dbp, cp->lock);
418 * Return the record number for a cursor.
421 __bam_c_rget(dbp, cp, key, data, flags)
432 /* Get the page with the current item on it. */
433 if ((ret = __bam_pget(dbp, &cp->page, &cp->pgno, 0)) != 0)
436 /* Get a copy of the key. */
437 memset(&dbt, 0, sizeof(DBT));
438 dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
439 if ((ret = __db_ret(dbp, cp->page, cp->indx, &dbt, NULL, NULL)) != 0)
443 if ((ret = __bam_search(dbp, &dbt, S_FIND, 1, &recno, &exact)) != 0)
447 ret = __db_retcopy(data, &recno, sizeof(recno),
448 &t->bt_rdata.data, &t->bt_rdata.ulen, dbp->db_malloc);
450 /* Release the stack. */
453 err: (void)memp_fput(dbp->mpf, cp->page, 0);
460 * Put using a cursor.
463 __bam_c_put(dbc, key, data, flags)
474 int exact, needkey, ret;
477 DEBUG_LWRITE(dbc->dbp, dbc->txn, "bam_c_put",
478 flags == DB_KEYFIRST || flags == DB_KEYLAST ? key : NULL,
483 if ((ret = __db_cputchk(dbc->dbp, key, data, flags,
484 F_ISSET(dbc->dbp, DB_AM_RDONLY), cp->pgno != PGNO_INVALID)) != 0)
487 GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
490 /* Initialize the cursor for a new retrieval. */
493 cp->lock = LOCK_INVALID;
496 * To split, we need a valid key for the page. Since it's a cursor,
497 * we have to build one.
500 split: if (needkey) {
501 memset(&dbt, 0, sizeof(DBT));
502 ret = __db_ret(dbp, cp->page, indx,
503 &dbt, &t->bt_rkey.data, &t->bt_rkey.ulen);
511 (void)__bam_stkrel(dbp);
514 if ((ret = __bam_split(dbp, arg)) != 0)
518 /* If there's no key supplied, use the cursor. */
519 if (flags == DB_KEYFIRST || flags == DB_KEYLAST)
523 if (cp->dpgno == PGNO_INVALID) {
530 /* Acquire the current page. */
531 if ((ret = __bam_lget(dbp,
532 0, cp->pgno, DB_LOCK_WRITE, &cp->lock)) != 0)
534 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
543 if ((ret = __bam_iitem(dbp, &cp->page,
544 &indx, key, data, flags, 0)) == DB_NEEDSPLIT)
550 __bam_c_search(dbp, cp, key, S_KEYFIRST, 0, &exact)) != 0)
553 indx = cp->dpgno == PGNO_INVALID ? cp->indx : cp->dindx;
554 if ((ret = __bam_iitem(dbp, &cp->page, &indx, key,
555 data, DB_BEFORE, exact ? 0 : BI_NEWKEY)) == DB_NEEDSPLIT)
563 __bam_c_search(dbp, cp, key, S_KEYLAST, 0, &exact)) != 0)
566 indx = cp->dpgno == PGNO_INVALID ? cp->indx : cp->dindx;
567 if ((ret = __bam_iitem(dbp, &cp->page, &indx, key,
568 data, DB_AFTER, exact ? 0 : BI_NEWKEY)) == DB_NEEDSPLIT)
576 * Update the cursor to point to the new entry. The new entry was
577 * stored on the current page, because we split pages until it was
580 if (cp->dpgno == PGNO_INVALID)
586 * If the previous cursor record has been deleted, delete it. The
587 * returned key isn't a deleted key, so clear the flag.
589 if (F_ISSET(©, C_DELETED) &&
590 (ret = __bam_c_physdel(dbp, ©, cp->page)) != 0)
592 F_CLR(cp, C_DELETED | C_REPLACE);
594 /* Release the previous lock, if any. */
595 if (copy.lock != LOCK_INVALID)
596 (void)__BT_TLPUT(dbp, copy.lock);
598 /* Discard the pinned page. */
599 ret = memp_fput(dbp->mpf, cp->page, 0);
601 err: if (cp->page != NULL)
602 (void)memp_fput(dbp->mpf, cp->page, 0);
603 if (cp->lock != LOCK_INVALID)
604 (void)__BT_TLPUT(dbp, cp->lock);
614 * Return the first record.
617 __bam_c_first(dbp, cp)
624 /* Walk down the left-hand side of the tree. */
625 for (pgno = PGNO_ROOT;;) {
627 __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
629 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
632 /* If we find a leaf page, we're done. */
633 if (ISLEAF(cp->page))
636 pgno = GET_BINTERNAL(cp->page, 0)->pgno;
640 cp->pgno = cp->page->pgno;
642 cp->dpgno = PGNO_INVALID;
644 /* If it's an empty page or a deleted record, go to the next one. */
645 if (NUM_ENT(cp->page) == 0 ||
646 B_DISSET(GET_BKEYDATA(cp->page, cp->indx + O_INDX)->type))
647 if ((ret = __bam_c_next(dbp, cp, 0)) != 0)
650 /* If it's a duplicate reference, go to the first entry. */
651 if ((ret = __bam_ovfl_chk(dbp, cp, O_INDX, 0)) != 0)
654 /* If it's a deleted record, go to the next one. */
655 if (cp->dpgno != PGNO_INVALID &&
656 B_DISSET(GET_BKEYDATA(cp->page, cp->dindx)->type))
657 if ((ret = __bam_c_next(dbp, cp, 0)) != 0)
664 * Return the last record.
667 __bam_c_last(dbp, cp)
674 /* Walk down the right-hand side of the tree. */
675 for (pgno = PGNO_ROOT;;) {
677 __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
679 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
682 /* If we find a leaf page, we're done. */
683 if (ISLEAF(cp->page))
687 GET_BINTERNAL(cp->page, NUM_ENT(cp->page) - O_INDX)->pgno;
691 cp->pgno = cp->page->pgno;
692 cp->indx = NUM_ENT(cp->page) == 0 ? 0 : NUM_ENT(cp->page) - P_INDX;
693 cp->dpgno = PGNO_INVALID;
695 /* If it's an empty page or a deleted record, go to the previous one. */
696 if (NUM_ENT(cp->page) == 0 ||
697 B_DISSET(GET_BKEYDATA(cp->page, cp->indx + O_INDX)->type))
698 if ((ret = __bam_c_prev(dbp, cp)) != 0)
701 /* If it's a duplicate reference, go to the last entry. */
702 if ((ret = __bam_ovfl_chk(dbp, cp, cp->indx + O_INDX, 1)) != 0)
705 /* If it's a deleted record, go to the previous one. */
706 if (cp->dpgno != PGNO_INVALID &&
707 B_DISSET(GET_BKEYDATA(cp->page, cp->dindx)->type))
708 if ((ret = __bam_c_prev(dbp, cp)) != 0)
715 * Move to the next record.
718 __bam_c_next(dbp, cp, initial_move)
723 db_indx_t adjust, indx;
728 * We're either moving through a page of duplicates or a btree leaf
731 if (cp->dpgno == PGNO_INVALID) {
732 adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
740 if (cp->page == NULL) {
742 __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
744 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
749 * If at the end of the page, move to a subsequent page.
752 * Check for >= NUM_ENT. If we're here as the result of a search that
753 * landed us on NUM_ENT, we'll increment indx before we test.
756 * This code handles empty pages and pages with only deleted entries.
761 if (indx >= NUM_ENT(cp->page)) {
762 pgno = cp->page->next_pgno;
766 * If we're in a btree leaf page, we've reached the end
767 * of the tree. If we've reached the end of a page of
768 * duplicates, continue from the btree leaf page where
769 * we found this page of duplicates.
771 if (pgno == PGNO_INVALID) {
772 /* If in a btree leaf page, it's EOF. */
773 if (cp->dpgno == PGNO_INVALID)
774 return (DB_NOTFOUND);
776 /* Continue from the last btree leaf page. */
777 cp->dpgno = PGNO_INVALID;
781 indx = cp->indx + P_INDX;
785 if ((ret = __bam_lget(dbp,
786 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
788 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
793 /* Ignore deleted records. */
794 if (dbp->type == DB_BTREE &&
795 ((cp->dpgno == PGNO_INVALID &&
796 B_DISSET(GET_BKEYDATA(cp->page, indx + O_INDX)->type)) ||
797 (cp->dpgno != PGNO_INVALID &&
798 B_DISSET(GET_BKEYDATA(cp->page, indx)->type)))) {
804 * If we're not in a duplicates page, check to see if we've
805 * found a page of duplicates, in which case we move to the
808 if (cp->dpgno == PGNO_INVALID) {
809 cp->pgno = cp->page->pgno;
813 __bam_ovfl_chk(dbp, cp, indx + O_INDX, 0)) != 0)
815 if (cp->dpgno != PGNO_INVALID) {
821 cp->dpgno = cp->page->pgno;
831 * Move to the previous record.
834 __bam_c_prev(dbp, cp)
838 db_indx_t indx, adjust;
843 * We're either moving through a page of duplicates or a btree leaf
846 if (cp->dpgno == PGNO_INVALID) {
847 adjust = dbp->type == DB_BTREE ? P_INDX : O_INDX;
855 if (cp->page == NULL) {
857 __bam_lget(dbp, 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
859 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
864 * If at the beginning of the page, move to any previous one.
867 * This code handles empty pages and pages with only deleted entries.
871 pgno = cp->page->prev_pgno;
875 * If we're in a btree leaf page, we've reached the
876 * beginning of the tree. If we've reached the first
877 * of a page of duplicates, continue from the btree
878 * leaf page where we found this page of duplicates.
880 if (pgno == PGNO_INVALID) {
881 /* If in a btree leaf page, it's SOF. */
882 if (cp->dpgno == PGNO_INVALID)
883 return (DB_NOTFOUND);
885 /* Continue from the last btree leaf page. */
886 cp->dpgno = PGNO_INVALID;
895 if ((ret = __bam_lget(dbp,
896 0, pgno, DB_LOCK_READ, &cp->lock)) != 0)
898 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
902 indx = NUM_ENT(cp->page);
907 /* Ignore deleted records. */
909 if (dbp->type == DB_BTREE &&
910 ((cp->dpgno == PGNO_INVALID &&
911 B_DISSET(GET_BKEYDATA(cp->page, indx + O_INDX)->type)) ||
912 (cp->dpgno != PGNO_INVALID &&
913 B_DISSET(GET_BKEYDATA(cp->page, indx)->type))))
917 * If we're not in a duplicates page, check to see if we've
918 * found a page of duplicates, in which case we move to the
921 if (cp->dpgno == PGNO_INVALID) {
922 cp->pgno = cp->page->pgno;
926 __bam_ovfl_chk(dbp, cp, indx + O_INDX, 1)) != 0)
928 if (cp->dpgno != PGNO_INVALID) {
929 indx = cp->dindx + O_INDX;
934 cp->dpgno = cp->page->pgno;
944 * Move to a specified record.
947 __bam_c_search(dbp, cp, key, flags, isrecno, exactp)
952 int isrecno, *exactp;
962 * Find any matching record; the search function pins the page. Make
963 * sure it's a valid key (__bam_search may return an index just past
964 * the end of a page) and return it.
967 if ((ret = __ram_getno(dbp, key, &recno, 0)) != 0)
969 ret = __bam_rsearch(dbp, &recno, flags, 1, exactp);
971 ret = __bam_search(dbp, key, flags, 1, NULL, exactp);
975 cp->page = t->bt_csp->page;
976 cp->pgno = cp->page->pgno;
977 cp->indx = t->bt_csp->indx;
978 cp->lock = t->bt_csp->lock;
979 cp->dpgno = PGNO_INVALID;
982 * If we have an exact match, make sure that we're not looking at a
983 * chain of duplicates -- if so, move to an entry in that chain.
986 if ((ret = __bam_ovfl_chk(dbp,
987 cp, cp->indx + O_INDX, LF_ISSET(S_DUPLAST))) != 0)
991 return (DB_NOTFOUND);
993 /* If past the end of a page, find the next entry. */
994 if (cp->indx == NUM_ENT(cp->page) &&
995 (ret = __bam_c_next(dbp, cp, 0)) != 0)
998 /* If it's a deleted record, go to the next or previous one. */
999 if (cp->dpgno != PGNO_INVALID &&
1000 B_DISSET(GET_BKEYDATA(cp->page, cp->dindx)->type))
1001 if (flags == S_KEYLAST) {
1002 if ((ret = __bam_c_prev(dbp, cp)) != 0)
1005 if ((ret = __bam_c_next(dbp, cp, 0)) != 0)
1012 * Check for an overflow record, and if found, move to the correct
1015 * PUBLIC: int __bam_ovfl_chk __P((DB *, CURSOR *, u_int32_t, int));
1018 __bam_ovfl_chk(dbp, cp, indx, to_end)
1028 /* Check for an overflow entry. */
1029 bo = GET_BOVERFLOW(cp->page, indx);
1030 if (B_TYPE(bo->type) != B_DUPLICATE)
1034 * If we find one, go to the duplicates page, and optionally move
1035 * to the last record on that page.
1038 * We don't lock duplicates pages, we've already got the correct
1039 * lock on the main page.
1042 if ((ret = memp_fput(dbp->mpf, cp->page, 0)) != 0)
1046 if ((ret = __db_dend(dbp, pgno, &cp->page)) != 0)
1048 indx = NUM_ENT(cp->page) - O_INDX;
1050 if ((ret = __bam_pget(dbp, &cp->page, &pgno, 0)) != 0)
1055 /* Update the duplicate entry in the cursor. */
1056 cp->dpgno = cp->page->pgno;
1065 * Display the current btree cursor list.
1074 DB_THREAD_LOCK(dbp);
1075 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1076 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1077 cp = (CURSOR *)dbc->internal;
1079 "%#0x: page: %lu index: %lu dpage %lu dindex: %lu",
1080 (u_int)cp, (u_long)cp->pgno, (u_long)cp->indx,
1081 (u_long)cp->dpgno, (u_long)cp->dindx);
1082 if (F_ISSET(cp, C_DELETED))
1083 fprintf(stderr, "(deleted)");
1084 fprintf(stderr, "\n");
1086 DB_THREAD_UNLOCK(dbp);
1092 * __bam_ca_delete --
1093 * Check if any of the cursors refer to the item we are about to delete.
1094 * We'll return the number of cursors that refer to the item in question.
1095 * If a cursor does refer to the item, then we set its deleted bit.
1097 * PUBLIC: int __bam_ca_delete __P((DB *, db_pgno_t, u_int32_t, CURSOR *));
1100 __bam_ca_delete(dbp, pgno, indx, curs)
1111 * Adjust the cursors. We don't have to review the cursors for any
1112 * process other than the current one, because we have the page write
1113 * locked at this point, and any other process had better be using a
1114 * different locker ID, meaning that only cursors in our process can
1117 * It's possible for multiple cursors within the thread to have write
1118 * locks on the same page, but, cursors within a thread must be single
1119 * threaded, so all we're locking here is the cursor linked list.
1121 * indx refers to the first of what might be a duplicate set. The
1122 * cursor passed in is the one initiating the delete, so we don't
1125 DB_THREAD_LOCK(dbp);
1126 for (count = 0, dbc = TAILQ_FIRST(&dbp->curs_queue);
1127 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1128 cp = (CURSOR *)dbc->internal;
1130 cp->pgno == pgno && cp->indx == indx) ||
1131 (cp->dpgno == pgno && cp->dindx == indx)) {
1133 F_SET(cp, C_DELETED);
1136 DB_THREAD_UNLOCK(dbp);
1142 * Adjust the cursors during a delete or insert.
1144 * PUBLIC: void __bam_ca_di __P((DB *, db_pgno_t, u_int32_t, int));
1147 __bam_ca_di(dbp, pgno, indx, value)
1156 /* Recno is responsible for its own adjustments. */
1157 if (dbp->type == DB_RECNO)
1161 * Adjust the cursors. See the comment in __bam_ca_delete().
1163 DB_THREAD_LOCK(dbp);
1164 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1165 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1166 cp = (CURSOR *)dbc->internal;
1167 if (cp->pgno == pgno && cp->indx >= indx)
1169 if (cp->dpgno == pgno && cp->dindx >= indx)
1172 DB_THREAD_UNLOCK(dbp);
1177 * Adjust the cursors when moving data items to a duplicates page.
1179 * PUBLIC: void __bam_ca_dup __P((DB *,
1180 * PUBLIC: db_pgno_t, u_int32_t, u_int32_t, db_pgno_t, u_int32_t));
1183 __bam_ca_dup(dbp, fpgno, first, fi, tpgno, ti)
1185 db_pgno_t fpgno, tpgno;
1186 u_int32_t first, fi, ti;
1192 * Adjust the cursors. See the comment in __bam_ca_delete().
1194 * No need to test duplicates, this only gets called when moving
1195 * leaf page data items onto a duplicates page.
1197 DB_THREAD_LOCK(dbp);
1198 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1199 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1200 cp = (CURSOR *)dbc->internal;
1202 * Ignore matching entries that have already been moved,
1203 * we move from the same location on the leaf page more
1206 if (cp->dpgno == PGNO_INVALID &&
1207 cp->pgno == fpgno && cp->indx == fi) {
1213 DB_THREAD_UNLOCK(dbp);
1218 * Adjust the cursors when moving data items to another page.
1220 * PUBLIC: void __bam_ca_move __P((DB *, BTREE *, db_pgno_t, db_pgno_t));
1223 __bam_ca_move(dbp, t, fpgno, tpgno)
1226 db_pgno_t fpgno, tpgno;
1231 /* Recno is responsible for its own adjustments. */
1232 if (dbp->type == DB_RECNO)
1236 * Adjust the cursors. See the comment in __bam_ca_delete().
1238 * No need to test duplicates, this only gets called when copying
1239 * over the root page with a leaf or internal page.
1241 DB_THREAD_LOCK(dbp);
1242 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1243 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1244 cp = (CURSOR *)dbc->internal;
1245 if (cp->pgno == fpgno)
1248 DB_THREAD_UNLOCK(dbp);
1252 * __bam_ca_replace --
1253 * Check if any of the cursors refer to the item we are about to replace.
1254 * If so, their flags should be changed from deleted to replaced.
1256 * PUBLIC: void __bam_ca_replace
1257 * PUBLIC: __P((DB *, db_pgno_t, u_int32_t, ca_replace_arg));
1260 __bam_ca_replace(dbp, pgno, indx, pass)
1264 ca_replace_arg pass;
1270 * Adjust the cursors. See the comment in __bam_ca_delete().
1272 * Find any cursors that have logically deleted a record we're about
1275 * Pass == REPLACE_SETUP:
1276 * Set C_REPLACE_SETUP so we can find the cursors again.
1278 * Pass == REPLACE_SUCCESS:
1279 * Clear C_DELETED and C_REPLACE_SETUP, set C_REPLACE, the
1280 * overwrite was successful.
1282 * Pass == REPLACE_FAILED:
1283 * Clear C_REPLACE_SETUP, the overwrite failed.
1285 * For REPLACE_SUCCESS and REPLACE_FAILED, we reset the indx value
1286 * for the cursor as it may have been changed by other cursor update
1287 * routines as the item was deleted/inserted.
1289 DB_THREAD_LOCK(dbp);
1291 case REPLACE_SETUP: /* Setup. */
1292 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1293 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1294 cp = (CURSOR *)dbc->internal;
1295 if ((cp->pgno == pgno && cp->indx == indx) ||
1296 (cp->dpgno == pgno && cp->dindx == indx))
1297 F_SET(cp, C_REPLACE_SETUP);
1300 case REPLACE_SUCCESS: /* Overwrite succeeded. */
1301 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1302 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1303 cp = (CURSOR *)dbc->internal;
1304 if (F_ISSET(cp, C_REPLACE_SETUP)) {
1305 if (cp->dpgno == pgno)
1307 if (cp->pgno == pgno)
1309 F_SET(cp, C_REPLACE);
1310 F_CLR(cp, C_DELETED | C_REPLACE_SETUP);
1314 case REPLACE_FAILED: /* Overwrite failed. */
1315 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1316 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1317 cp = (CURSOR *)dbc->internal;
1318 if (F_ISSET(cp, C_REPLACE_SETUP)) {
1319 if (cp->dpgno == pgno)
1321 if (cp->pgno == pgno)
1323 F_CLR(cp, C_REPLACE_SETUP);
1328 DB_THREAD_UNLOCK(dbp);
1333 * Adjust the cursors when splitting a page.
1335 * PUBLIC: void __bam_ca_split __P((DB *,
1336 * PUBLIC: db_pgno_t, db_pgno_t, db_pgno_t, u_int32_t, int));
1339 __bam_ca_split(dbp, ppgno, lpgno, rpgno, split_indx, cleft)
1341 db_pgno_t ppgno, lpgno, rpgno;
1342 u_int32_t split_indx;
1348 /* Recno is responsible for its own adjustments. */
1349 if (dbp->type == DB_RECNO)
1353 * Adjust the cursors. See the comment in __bam_ca_delete().
1355 * If splitting the page that a cursor was on, the cursor has to be
1356 * adjusted to point to the same record as before the split. Most
1357 * of the time we don't adjust pointers to the left page, because
1358 * we're going to copy its contents back over the original page. If
1359 * the cursor is on the right page, it is decremented by the number of
1360 * records split to the left page.
1362 DB_THREAD_LOCK(dbp);
1363 for (dbc = TAILQ_FIRST(&dbp->curs_queue);
1364 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
1365 cp = (CURSOR *)dbc->internal;
1366 if (cp->pgno == ppgno)
1367 if (cp->indx < split_indx) {
1372 cp->indx -= split_indx;
1374 if (cp->dpgno == ppgno)
1375 if (cp->dindx < split_indx) {
1380 cp->dindx -= split_indx;
1383 DB_THREAD_UNLOCK(dbp);
1387 * __bam_c_physdel --
1388 * Actually do the cursor deletion.
1391 __bam_c_physdel(dbp, cp, h)
1401 db_pgno_t pgno, next_pgno, prev_pgno;
1407 /* Figure out what we're deleting. */
1408 if (cp->dpgno == PGNO_INVALID) {
1417 * If the item is referenced by another cursor, leave it up to that
1418 * cursor to do the delete.
1420 if (__bam_ca_delete(dbp, pgno, indx, cp) != 0)
1424 * If we don't already have the page locked, get it and delete the
1427 if ((h == NULL || h->pgno != pgno)) {
1428 if ((ret = __bam_lget(dbp, 0, pgno, DB_LOCK_WRITE, &lock)) != 0)
1430 if ((ret = __bam_pget(dbp, &h, &pgno, 0)) != 0)
1437 * If we're deleting a duplicate entry, call the common code to do
1440 if (TYPE(h) == P_DUPLICATE) {
1442 prev_pgno = PREV_PGNO(h);
1443 next_pgno = NEXT_PGNO(h);
1444 if ((ret = __db_drem(dbp, &h, indx, __bam_free)) != 0)
1448 * There are 4 cases:
1450 * 1. We removed an item on a page, but there are more items
1452 * 2. We removed the last item on a page, removing the last
1454 * 3. We removed the last item on a page, but there is a
1455 * following page of duplicates.
1456 * 4. We removed the last item on a page, but there is a
1457 * previous page of duplicates.
1459 * In case 1, h != NULL, h->pgno == pgno
1460 * In case 2, h == NULL,
1461 * prev_pgno == PGNO_INVALID, next_pgno == PGNO_INVALID
1462 * In case 3, h != NULL, next_pgno != PGNO_INVALID
1463 * In case 4, h == NULL, prev_pgno != PGNO_INVALID
1465 * In case 1, there's nothing else to do.
1466 * In case 2, remove the entry from the parent page.
1467 * In case 3 or 4, if the deleted page was the first in a chain
1468 * of duplicate pages, update the parent page's entry.
1471 * If there were previous pages of duplicates or we didn't
1472 * empty the current page of duplicates, we don't need to
1473 * touch the parent page.
1475 if (PREV_PGNO(h) != PGNO_INVALID ||
1476 (h != NULL && pgno == h->pgno))
1480 * Release any page we're holding and the lock on the deleted
1485 (void)memp_fput(dbp->mpf, h, 0);
1486 (void)__BT_TLPUT(dbp, lock);
1490 /* Acquire the parent page. */
1492 __bam_lget(dbp, 0, cp->pgno, DB_LOCK_WRITE, &lock)) != 0)
1494 if ((ret = __bam_pget(dbp, &h, &cp->pgno, 0)) != 0) {
1495 (void)__BT_TLPUT(dbp, lock);
1501 * If we deleted the last duplicate, we can fall out and do a
1502 * normal btree delete in the context of the parent page. If
1503 * not, we have to update the parent's page.
1506 if (next_pgno != PGNO_INVALID) {
1508 * Copy, delete, update and re-insert the parent page's
1511 bo = *GET_BOVERFLOW(h, indx);
1512 (void)__db_ditem(dbp, h, indx, BOVERFLOW_SIZE);
1513 bo.pgno = next_pgno;
1514 memset(&dbt, 0, sizeof(dbt));
1516 dbt.size = BOVERFLOW_SIZE;
1517 (void)__db_pitem(dbp,
1518 h, indx, BOVERFLOW_SIZE, &dbt, NULL);
1520 /* Discard the parent page. */
1521 (void)memp_fput(dbp->mpf, h, 0);
1522 (void)__BT_TLPUT(dbp, lock);
1529 /* Otherwise, do a normal btree delete. */
1530 if ((ret = __bam_ditem(dbp, h, indx)) != 0)
1532 if ((ret = __bam_ditem(dbp, h, indx)) != 0)
1536 * If the page is empty, delete it. To delete a leaf page we need a
1537 * copy of a key from the page. We use the first one that was there,
1538 * since it's the last key that the page held. We malloc the page
1539 * information instead of using the return key/data memory because
1540 * we've already set them -- the reason that we've already set them
1541 * is because we're (potentially) about to do a reverse split, which
1542 * would make our saved page information useless.
1545 * The following operations to delete a page might deadlock. I think
1546 * that's OK. The problem is if we're deleting an item because we're
1547 * closing cursors because we've already deadlocked and want to call
1548 * txn_abort(). If we fail due to deadlock, we'll leave an locked
1549 * empty page in the tree, which won't be empty long because we're
1550 * going to undo the delete.
1552 if (NUM_ENT(h) == 0 && h->pgno != PGNO_ROOT) {
1553 memset(&dbt, 0, sizeof(DBT));
1554 dbt.flags = DB_DBT_MALLOC | DB_DBT_INTERNAL;
1555 if ((ret = __db_ret(dbp, h, 0, &dbt, NULL, NULL)) != 0)
1559 (void)memp_fput(dbp->mpf, h, 0);
1560 (void)__BT_TLPUT(dbp, lock);
1564 ret = __bam_dpage(dbp, &dbt);
1570 (void)memp_fput(dbp->mpf, h, 0);
1571 (void)__BT_TLPUT(dbp, lock);
1575 ++t->lstat.bt_deleted;