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