1*0Sstevel@tonic-gate /*-
2*0Sstevel@tonic-gate * See the file LICENSE for redistribution information.
3*0Sstevel@tonic-gate *
4*0Sstevel@tonic-gate * Copyright (c) 1996, 1997, 1998
5*0Sstevel@tonic-gate * Sleepycat Software. All rights reserved.
6*0Sstevel@tonic-gate */
7*0Sstevel@tonic-gate
8*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
9*0Sstevel@tonic-gate
10*0Sstevel@tonic-gate #include "config.h"
11*0Sstevel@tonic-gate
12*0Sstevel@tonic-gate #ifndef lint
13*0Sstevel@tonic-gate static const char sccsid[] = "@(#)bt_curadj.c 10.69 (Sleepycat) 12/2/98";
14*0Sstevel@tonic-gate #endif /* not lint */
15*0Sstevel@tonic-gate
16*0Sstevel@tonic-gate #ifndef NO_SYSTEM_INCLUDES
17*0Sstevel@tonic-gate #include <sys/types.h>
18*0Sstevel@tonic-gate
19*0Sstevel@tonic-gate #include <stdlib.h>
20*0Sstevel@tonic-gate #endif
21*0Sstevel@tonic-gate
22*0Sstevel@tonic-gate #include "db_int.h"
23*0Sstevel@tonic-gate #include "db_page.h"
24*0Sstevel@tonic-gate #include "btree.h"
25*0Sstevel@tonic-gate
26*0Sstevel@tonic-gate #ifdef DEBUG
27*0Sstevel@tonic-gate /*
28*0Sstevel@tonic-gate * __bam_cprint --
29*0Sstevel@tonic-gate * Display the current cursor list.
30*0Sstevel@tonic-gate *
31*0Sstevel@tonic-gate * PUBLIC: int __bam_cprint __P((DB *));
32*0Sstevel@tonic-gate */
33*0Sstevel@tonic-gate int
__bam_cprint(dbp)34*0Sstevel@tonic-gate __bam_cprint(dbp)
35*0Sstevel@tonic-gate DB *dbp;
36*0Sstevel@tonic-gate {
37*0Sstevel@tonic-gate CURSOR *cp;
38*0Sstevel@tonic-gate DBC *dbc;
39*0Sstevel@tonic-gate
40*0Sstevel@tonic-gate DB_THREAD_LOCK(dbp);
41*0Sstevel@tonic-gate for (dbc = TAILQ_FIRST(&dbp->active_queue);
42*0Sstevel@tonic-gate dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
43*0Sstevel@tonic-gate cp = (CURSOR *)dbc->internal;
44*0Sstevel@tonic-gate fprintf(stderr,
45*0Sstevel@tonic-gate "%#0x->%#0x: page: %lu index: %lu dpage %lu dindex: %lu recno: %lu",
46*0Sstevel@tonic-gate (u_int)dbc, (u_int)cp, (u_long)cp->pgno, (u_long)cp->indx,
47*0Sstevel@tonic-gate (u_long)cp->dpgno, (u_long)cp->dindx, (u_long)cp->recno);
48*0Sstevel@tonic-gate if (F_ISSET(cp, C_DELETED))
49*0Sstevel@tonic-gate fprintf(stderr, " (deleted)");
50*0Sstevel@tonic-gate fprintf(stderr, "\n");
51*0Sstevel@tonic-gate }
52*0Sstevel@tonic-gate DB_THREAD_UNLOCK(dbp);
53*0Sstevel@tonic-gate
54*0Sstevel@tonic-gate return (0);
55*0Sstevel@tonic-gate }
56*0Sstevel@tonic-gate #endif /* DEBUG */
57*0Sstevel@tonic-gate
58*0Sstevel@tonic-gate /*
59*0Sstevel@tonic-gate * __bam_ca_delete --
60*0Sstevel@tonic-gate * Update the cursors when items are deleted and when already deleted
61*0Sstevel@tonic-gate * items are overwritten. Return the number of relevant cursors found.
62*0Sstevel@tonic-gate *
63*0Sstevel@tonic-gate * PUBLIC: int __bam_ca_delete __P((DB *, db_pgno_t, u_int32_t, int));
64*0Sstevel@tonic-gate */
65*0Sstevel@tonic-gate int
__bam_ca_delete(dbp,pgno,indx,delete)66*0Sstevel@tonic-gate __bam_ca_delete(dbp, pgno, indx, delete)
67*0Sstevel@tonic-gate DB *dbp;
68*0Sstevel@tonic-gate db_pgno_t pgno;
69*0Sstevel@tonic-gate u_int32_t indx;
70*0Sstevel@tonic-gate int delete;
71*0Sstevel@tonic-gate {
72*0Sstevel@tonic-gate DBC *dbc;
73*0Sstevel@tonic-gate CURSOR *cp;
74*0Sstevel@tonic-gate int count; /* !!!: Has to contain max number of cursors. */
75*0Sstevel@tonic-gate
76*0Sstevel@tonic-gate /* Recno is responsible for its own adjustments. */
77*0Sstevel@tonic-gate if (dbp->type == DB_RECNO)
78*0Sstevel@tonic-gate return (0);
79*0Sstevel@tonic-gate
80*0Sstevel@tonic-gate /*
81*0Sstevel@tonic-gate * Adjust the cursors. We don't have to review the cursors for any
82*0Sstevel@tonic-gate * thread of control other than the current one, because we have the
83*0Sstevel@tonic-gate * page write locked at this point, and any other thread of control
84*0Sstevel@tonic-gate * had better be using a different locker ID, meaning only cursors in
85*0Sstevel@tonic-gate * our thread of control can be on the page.
86*0Sstevel@tonic-gate *
87*0Sstevel@tonic-gate * It's possible for multiple cursors within the thread to have write
88*0Sstevel@tonic-gate * locks on the same page, but, cursors within a thread must be single
89*0Sstevel@tonic-gate * threaded, so all we're locking here is the cursor linked list.
90*0Sstevel@tonic-gate */
91*0Sstevel@tonic-gate DB_THREAD_LOCK(dbp);
92*0Sstevel@tonic-gate for (count = 0, dbc = TAILQ_FIRST(&dbp->active_queue);
93*0Sstevel@tonic-gate dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
94*0Sstevel@tonic-gate cp = (CURSOR *)dbc->internal;
95*0Sstevel@tonic-gate
96*0Sstevel@tonic-gate if ((cp->pgno == pgno && cp->indx == indx) ||
97*0Sstevel@tonic-gate (cp->dpgno == pgno && cp->dindx == indx)) {
98*0Sstevel@tonic-gate if (delete)
99*0Sstevel@tonic-gate F_SET(cp, C_DELETED);
100*0Sstevel@tonic-gate else
101*0Sstevel@tonic-gate F_CLR(cp, C_DELETED);
102*0Sstevel@tonic-gate ++count;
103*0Sstevel@tonic-gate }
104*0Sstevel@tonic-gate }
105*0Sstevel@tonic-gate DB_THREAD_UNLOCK(dbp);
106*0Sstevel@tonic-gate
107*0Sstevel@tonic-gate return (count);
108*0Sstevel@tonic-gate }
109*0Sstevel@tonic-gate
110*0Sstevel@tonic-gate /*
111*0Sstevel@tonic-gate * __bam_ca_di --
112*0Sstevel@tonic-gate * Adjust the cursors during a delete or insert.
113*0Sstevel@tonic-gate *
114*0Sstevel@tonic-gate * PUBLIC: void __bam_ca_di __P((DB *, db_pgno_t, u_int32_t, int));
115*0Sstevel@tonic-gate */
116*0Sstevel@tonic-gate void
__bam_ca_di(dbp,pgno,indx,adjust)117*0Sstevel@tonic-gate __bam_ca_di(dbp, pgno, indx, adjust)
118*0Sstevel@tonic-gate DB *dbp;
119*0Sstevel@tonic-gate db_pgno_t pgno;
120*0Sstevel@tonic-gate u_int32_t indx;
121*0Sstevel@tonic-gate int adjust;
122*0Sstevel@tonic-gate {
123*0Sstevel@tonic-gate CURSOR *cp;
124*0Sstevel@tonic-gate DBC *dbc;
125*0Sstevel@tonic-gate
126*0Sstevel@tonic-gate /* Recno is responsible for its own adjustments. */
127*0Sstevel@tonic-gate if (dbp->type == DB_RECNO)
128*0Sstevel@tonic-gate return;
129*0Sstevel@tonic-gate
130*0Sstevel@tonic-gate /*
131*0Sstevel@tonic-gate * Adjust the cursors. See the comment in __bam_ca_delete().
132*0Sstevel@tonic-gate */
133*0Sstevel@tonic-gate DB_THREAD_LOCK(dbp);
134*0Sstevel@tonic-gate for (dbc = TAILQ_FIRST(&dbp->active_queue);
135*0Sstevel@tonic-gate dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
136*0Sstevel@tonic-gate cp = (CURSOR *)dbc->internal;
137*0Sstevel@tonic-gate if (cp->pgno == pgno && cp->indx >= indx)
138*0Sstevel@tonic-gate cp->indx += adjust;
139*0Sstevel@tonic-gate if (cp->dpgno == pgno && cp->dindx >= indx)
140*0Sstevel@tonic-gate cp->dindx += adjust;
141*0Sstevel@tonic-gate }
142*0Sstevel@tonic-gate DB_THREAD_UNLOCK(dbp);
143*0Sstevel@tonic-gate }
144*0Sstevel@tonic-gate
145*0Sstevel@tonic-gate /*
146*0Sstevel@tonic-gate * __bam_ca_dup --
147*0Sstevel@tonic-gate * Adjust the cursors when moving items from a leaf page to a duplicates
148*0Sstevel@tonic-gate * page.
149*0Sstevel@tonic-gate *
150*0Sstevel@tonic-gate * PUBLIC: void __bam_ca_dup __P((DB *,
151*0Sstevel@tonic-gate * PUBLIC: db_pgno_t, u_int32_t, u_int32_t, db_pgno_t, u_int32_t));
152*0Sstevel@tonic-gate */
153*0Sstevel@tonic-gate void
__bam_ca_dup(dbp,fpgno,first,fi,tpgno,ti)154*0Sstevel@tonic-gate __bam_ca_dup(dbp, fpgno, first, fi, tpgno, ti)
155*0Sstevel@tonic-gate DB *dbp;
156*0Sstevel@tonic-gate db_pgno_t fpgno, tpgno;
157*0Sstevel@tonic-gate u_int32_t first, fi, ti;
158*0Sstevel@tonic-gate {
159*0Sstevel@tonic-gate CURSOR *cp;
160*0Sstevel@tonic-gate DBC *dbc;
161*0Sstevel@tonic-gate
162*0Sstevel@tonic-gate /* Recno is responsible for its own adjustments. */
163*0Sstevel@tonic-gate if (dbp->type == DB_RECNO)
164*0Sstevel@tonic-gate return;
165*0Sstevel@tonic-gate
166*0Sstevel@tonic-gate /*
167*0Sstevel@tonic-gate * Adjust the cursors. See the comment in __bam_ca_delete().
168*0Sstevel@tonic-gate */
169*0Sstevel@tonic-gate DB_THREAD_LOCK(dbp);
170*0Sstevel@tonic-gate for (dbc = TAILQ_FIRST(&dbp->active_queue);
171*0Sstevel@tonic-gate dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
172*0Sstevel@tonic-gate cp = (CURSOR *)dbc->internal;
173*0Sstevel@tonic-gate /*
174*0Sstevel@tonic-gate * Ignore matching entries that have already been moved,
175*0Sstevel@tonic-gate * we move from the same location on the leaf page more
176*0Sstevel@tonic-gate * than once.
177*0Sstevel@tonic-gate */
178*0Sstevel@tonic-gate if (cp->dpgno == PGNO_INVALID &&
179*0Sstevel@tonic-gate cp->pgno == fpgno && cp->indx == fi) {
180*0Sstevel@tonic-gate cp->indx = first;
181*0Sstevel@tonic-gate cp->dpgno = tpgno;
182*0Sstevel@tonic-gate cp->dindx = ti;
183*0Sstevel@tonic-gate }
184*0Sstevel@tonic-gate }
185*0Sstevel@tonic-gate DB_THREAD_UNLOCK(dbp);
186*0Sstevel@tonic-gate }
187*0Sstevel@tonic-gate
188*0Sstevel@tonic-gate /*
189*0Sstevel@tonic-gate * __bam_ca_rsplit --
190*0Sstevel@tonic-gate * Adjust the cursors when doing reverse splits.
191*0Sstevel@tonic-gate *
192*0Sstevel@tonic-gate * PUBLIC: void __bam_ca_rsplit __P((DB *, db_pgno_t, db_pgno_t));
193*0Sstevel@tonic-gate */
194*0Sstevel@tonic-gate void
__bam_ca_rsplit(dbp,fpgno,tpgno)195*0Sstevel@tonic-gate __bam_ca_rsplit(dbp, fpgno, tpgno)
196*0Sstevel@tonic-gate DB *dbp;
197*0Sstevel@tonic-gate db_pgno_t fpgno, tpgno;
198*0Sstevel@tonic-gate {
199*0Sstevel@tonic-gate CURSOR *cp;
200*0Sstevel@tonic-gate DBC *dbc;
201*0Sstevel@tonic-gate
202*0Sstevel@tonic-gate /* Recno is responsible for its own adjustments. */
203*0Sstevel@tonic-gate if (dbp->type == DB_RECNO)
204*0Sstevel@tonic-gate return;
205*0Sstevel@tonic-gate
206*0Sstevel@tonic-gate /*
207*0Sstevel@tonic-gate * Adjust the cursors. See the comment in __bam_ca_delete().
208*0Sstevel@tonic-gate */
209*0Sstevel@tonic-gate DB_THREAD_LOCK(dbp);
210*0Sstevel@tonic-gate for (dbc = TAILQ_FIRST(&dbp->active_queue);
211*0Sstevel@tonic-gate dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
212*0Sstevel@tonic-gate cp = (CURSOR *)dbc->internal;
213*0Sstevel@tonic-gate if (cp->pgno == fpgno)
214*0Sstevel@tonic-gate cp->pgno = tpgno;
215*0Sstevel@tonic-gate }
216*0Sstevel@tonic-gate DB_THREAD_UNLOCK(dbp);
217*0Sstevel@tonic-gate }
218*0Sstevel@tonic-gate
219*0Sstevel@tonic-gate /*
220*0Sstevel@tonic-gate * __bam_ca_split --
221*0Sstevel@tonic-gate * Adjust the cursors when splitting a page.
222*0Sstevel@tonic-gate *
223*0Sstevel@tonic-gate * PUBLIC: void __bam_ca_split __P((DB *,
224*0Sstevel@tonic-gate * PUBLIC: db_pgno_t, db_pgno_t, db_pgno_t, u_int32_t, int));
225*0Sstevel@tonic-gate */
226*0Sstevel@tonic-gate void
__bam_ca_split(dbp,ppgno,lpgno,rpgno,split_indx,cleft)227*0Sstevel@tonic-gate __bam_ca_split(dbp, ppgno, lpgno, rpgno, split_indx, cleft)
228*0Sstevel@tonic-gate DB *dbp;
229*0Sstevel@tonic-gate db_pgno_t ppgno, lpgno, rpgno;
230*0Sstevel@tonic-gate u_int32_t split_indx;
231*0Sstevel@tonic-gate int cleft;
232*0Sstevel@tonic-gate {
233*0Sstevel@tonic-gate DBC *dbc;
234*0Sstevel@tonic-gate CURSOR *cp;
235*0Sstevel@tonic-gate
236*0Sstevel@tonic-gate /* Recno is responsible for its own adjustments. */
237*0Sstevel@tonic-gate if (dbp->type == DB_RECNO)
238*0Sstevel@tonic-gate return;
239*0Sstevel@tonic-gate
240*0Sstevel@tonic-gate /*
241*0Sstevel@tonic-gate * Adjust the cursors. See the comment in __bam_ca_delete().
242*0Sstevel@tonic-gate *
243*0Sstevel@tonic-gate * If splitting the page that a cursor was on, the cursor has to be
244*0Sstevel@tonic-gate * adjusted to point to the same record as before the split. Most
245*0Sstevel@tonic-gate * of the time we don't adjust pointers to the left page, because
246*0Sstevel@tonic-gate * we're going to copy its contents back over the original page. If
247*0Sstevel@tonic-gate * the cursor is on the right page, it is decremented by the number of
248*0Sstevel@tonic-gate * records split to the left page.
249*0Sstevel@tonic-gate */
250*0Sstevel@tonic-gate DB_THREAD_LOCK(dbp);
251*0Sstevel@tonic-gate for (dbc = TAILQ_FIRST(&dbp->active_queue);
252*0Sstevel@tonic-gate dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
253*0Sstevel@tonic-gate cp = (CURSOR *)dbc->internal;
254*0Sstevel@tonic-gate if (cp->pgno == ppgno)
255*0Sstevel@tonic-gate if (cp->indx < split_indx) {
256*0Sstevel@tonic-gate if (cleft)
257*0Sstevel@tonic-gate cp->pgno = lpgno;
258*0Sstevel@tonic-gate } else {
259*0Sstevel@tonic-gate cp->pgno = rpgno;
260*0Sstevel@tonic-gate cp->indx -= split_indx;
261*0Sstevel@tonic-gate }
262*0Sstevel@tonic-gate if (cp->dpgno == ppgno)
263*0Sstevel@tonic-gate if (cp->dindx < split_indx) {
264*0Sstevel@tonic-gate if (cleft)
265*0Sstevel@tonic-gate cp->dpgno = lpgno;
266*0Sstevel@tonic-gate } else {
267*0Sstevel@tonic-gate cp->dpgno = rpgno;
268*0Sstevel@tonic-gate cp->dindx -= split_indx;
269*0Sstevel@tonic-gate }
270*0Sstevel@tonic-gate }
271*0Sstevel@tonic-gate DB_THREAD_UNLOCK(dbp);
272*0Sstevel@tonic-gate }
273