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