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