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