bt_curadj.c

Go to the documentation of this file.
00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1996, 1997, 1998, 1999, 2000
00005  *      Sleepycat Software.  All rights reserved.
00006  */
00007 
00008 #include "config.h"
00009 
00010 #ifndef lint
00011 static const char revid[] = "$Id: bt__curadj_8c-source.html,v 1.1 2008/06/08 10:13:30 sebdiaz Exp $";
00012 #endif /* not lint */
00013 
00014 #ifndef NO_SYSTEM_INCLUDES
00015 #include <sys/types.h>
00016 #endif
00017 
00018 #include "db_int.h"
00019 #include "db_page.h"
00020 #include "btree.h"
00021 
00022 static int __bam_opd_cursor __P((DB *, DBC *, db_pgno_t, u_int32_t, u_int32_t));
00023 
00024 #ifdef DEBUG
00025 /*
00026  * CDB___bam_cprint --
00027  *      Display the current internal cursor.
00028  *
00029  * PUBLIC: void CDB___bam_cprint __P((DBC *));
00030  */
00031 void
00032 CDB___bam_cprint(dbc)
00033         DBC *dbc;
00034 {
00035         BTREE_CURSOR *cp;
00036 
00037         cp = (BTREE_CURSOR *)dbc->internal;
00038 
00039         fprintf(stderr, "\tinternal: ovflsize: %lu", (u_long)cp->ovflsize);
00040         if (dbc->dbtype == DB_RECNO)
00041                 fprintf(stderr, " recno: %lu", (u_long)cp->recno);
00042         if (F_ISSET(cp, C_DELETED))
00043                 fprintf(stderr, " (deleted)");
00044         fprintf(stderr, "\n");
00045 }
00046 #endif
00047 
00048 /*
00049  * CDB___bam_ca_delete --
00050  *      Update the cursors when items are deleted and when already deleted
00051  *      items are overwritten.  Return the number of relevant cursors found.
00052  *
00053  * PUBLIC: int CDB___bam_ca_delete __P((DB *, db_pgno_t, u_int32_t, int));
00054  */
00055 int
00056 CDB___bam_ca_delete(dbp, pgno, indx, delete)
00057         DB *dbp;
00058         db_pgno_t pgno;
00059         u_int32_t indx;
00060         int delete;
00061 {
00062         BTREE_CURSOR *cp;
00063         DBC *dbc;
00064         int count;              /* !!!: Has to contain max number of cursors. */
00065 
00066         /*
00067          * Adjust the cursors.  We don't have to review the cursors for any
00068          * thread of control other than the current one, because we have the
00069          * page write locked at this point, and any other thread of control
00070          * had better be using a different locker ID, meaning only cursors in
00071          * our thread of control can be on the page.
00072          *
00073          * It's possible for multiple cursors within the thread to have write
00074          * locks on the same page, but, cursors within a thread must be single
00075          * threaded, so all we're locking here is the cursor linked list.
00076          */
00077         MUTEX_THREAD_LOCK(dbp->mutexp);
00078         for (count = 0, dbc = TAILQ_FIRST(&dbp->active_queue);
00079             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
00080                 cp = (BTREE_CURSOR *)dbc->internal;
00081                 if (cp->pgno == pgno && cp->indx == indx) {
00082                         if (delete)
00083                                 F_SET(cp, C_DELETED);
00084                         else
00085                                 F_CLR(cp, C_DELETED);
00086                         ++count;
00087                 }
00088         }
00089         MUTEX_THREAD_UNLOCK(dbp->mutexp);
00090 
00091         return (count);
00092 }
00093 
00094 /*
00095  * CDB___ram_ca_delete --
00096  *      Return the number of relevant cursors.
00097  *
00098  * PUBLIC: int CDB___ram_ca_delete __P((DB *, db_pgno_t));
00099  */
00100 int
00101 CDB___ram_ca_delete(dbp, root_pgno)
00102         DB *dbp;
00103         db_pgno_t root_pgno;
00104 {
00105         DBC *dbc;
00106 
00107         /*
00108          * Review the cursors.  See the comment in CDB___bam_ca_delete().
00109          */
00110         MUTEX_THREAD_LOCK(dbp->mutexp);
00111         for (dbc = TAILQ_FIRST(&dbp->active_queue);
00112             dbc != NULL; dbc = TAILQ_NEXT(dbc, links))
00113                 if (dbc->internal->root == root_pgno)
00114                         break;
00115         MUTEX_THREAD_UNLOCK(dbp->mutexp);
00116         return (dbc == NULL ? 0 : 1);
00117 }
00118 
00119 /*
00120  * CDB___bam_ca_di --
00121  *      Adjust the cursors during a delete or insert.
00122  *
00123  * PUBLIC: void CDB___bam_ca_di __P((DB *, db_pgno_t, u_int32_t, int));
00124  */
00125 void
00126 CDB___bam_ca_di(dbp, pgno, indx, adjust)
00127         DB *dbp;
00128         db_pgno_t pgno;
00129         u_int32_t indx;
00130         int adjust;
00131 {
00132         DBC *dbc;
00133         DBC_INTERNAL *cp;
00134 
00135         /*
00136          * Adjust the cursors.  See the comment in CDB___bam_ca_delete().
00137          */
00138         MUTEX_THREAD_LOCK(dbp->mutexp);
00139         for (dbc = TAILQ_FIRST(&dbp->active_queue);
00140             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
00141                 if (dbc->dbtype == DB_RECNO)
00142                         continue;
00143                 cp = dbc->internal;
00144                 if (cp->pgno == pgno && cp->indx >= indx) {
00145                         /* Cursor indices should never be negative. */
00146                         DB_ASSERT(cp->indx != 0 || adjust > 0);
00147 
00148                         cp->indx += adjust;
00149                 }
00150         }
00151         MUTEX_THREAD_UNLOCK(dbp->mutexp);
00152 }
00153 
00154 /*
00155  * __bam_opd_cursor -- create a new opd cursor.
00156  */
00157 static int
00158 __bam_opd_cursor(dbp, dbc, first, tpgno, ti)
00159         DB *dbp;
00160         DBC *dbc;
00161         db_pgno_t tpgno;
00162         u_int32_t first, ti;
00163 {
00164         BTREE_CURSOR *cp, *orig_cp;
00165         DBC *dbc_nopd;
00166         int ret;
00167 
00168         orig_cp = (BTREE_CURSOR *)dbc->internal;
00169         dbc_nopd = NULL;
00170 
00171         /*
00172          * Allocate a new cursor and create the stack.  If duplicates
00173          * are sorted, we've just created an off-page duplicate Btree.
00174          * If duplicates aren't sorted, we've just created a Recno tree.
00175          */
00176         if ((ret = CDB___db_icursor(dbp, dbc->txn,
00177             dbp->dup_compare == NULL ? DB_RECNO : DB_BTREE,
00178             tpgno, 1, &dbc_nopd)) != 0)
00179                 return (ret);
00180 
00181         cp = (BTREE_CURSOR *)dbc_nopd->internal;
00182         cp->pgno = tpgno;
00183         cp->indx = ti;
00184 
00185         if (dbp->dup_compare == NULL) {
00186                 /*
00187                  * Converting to off-page Recno trees is tricky.  The
00188                  * record number for the cursor is the index + 1 (to
00189                  * convert to 1-based record numbers).
00190                  */
00191                 cp->recno = ti + 1;
00192         }
00193 
00194         /*
00195          * Transfer the deleted flag from the top-level cursor to the
00196          * created one.
00197          */
00198         if (F_ISSET(orig_cp, C_DELETED)) {
00199                 F_SET(cp, C_DELETED);
00200                 F_CLR(orig_cp, C_DELETED);
00201         }
00202 
00203         /* Stack the cursors and reset the initial cursor's index. */
00204         orig_cp->opd = dbc_nopd;
00205         orig_cp->indx = first;
00206         return (0);
00207 }
00208 
00209 /*
00210  * CDB___bam_ca_dup --
00211  *      Adjust the cursors when moving items from a leaf page to a duplicates
00212  *      page.
00213  *
00214  * PUBLIC: int CDB___bam_ca_dup __P((DB *,
00215  * PUBLIC:    db_pgno_t, u_int32_t, u_int32_t, db_pgno_t, u_int32_t));
00216  */
00217 int
00218 CDB___bam_ca_dup(dbp, first, fpgno, fi, tpgno, ti)
00219         DB *dbp;
00220         db_pgno_t fpgno, tpgno;
00221         u_int32_t first, fi, ti;
00222 {
00223         BTREE_CURSOR *orig_cp;
00224         DBC *dbc;
00225         int ret;
00226 
00227         /*
00228          * Adjust the cursors.  See the comment in CDB___bam_ca_delete().
00229          */
00230 loop:
00231         MUTEX_THREAD_LOCK(dbp->mutexp);
00232         for (dbc = TAILQ_FIRST(&dbp->active_queue);
00233             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
00234                 /*
00235                  * Ignore matching entries that have already been moved,
00236                  * we move from the same location on the leaf page more
00237                  * than once.
00238                  */
00239                 orig_cp = (BTREE_CURSOR *)dbc->internal;
00240                 if (orig_cp->opd != NULL ||
00241                     orig_cp->pgno != fpgno || orig_cp->indx != fi)
00242                         continue;
00243 
00244                 MUTEX_THREAD_UNLOCK(dbp->mutexp);
00245                 if ((ret = __bam_opd_cursor(dbp, dbc, first, tpgno, ti)) !=0)
00246                         return (ret);
00247                 /* We released the MUTEX to get a cursor, start over. */
00248                 goto loop;
00249         }
00250         MUTEX_THREAD_UNLOCK(dbp->mutexp);
00251 
00252         return (0);
00253 }
00254 
00255 /*
00256  * CDB___bam_ca_rsplit --
00257  *      Adjust the cursors when doing reverse splits.
00258  *
00259  * PUBLIC: void CDB___bam_ca_rsplit __P((DB *, db_pgno_t, db_pgno_t));
00260  */
00261 void
00262 CDB___bam_ca_rsplit(dbp, fpgno, tpgno)
00263         DB *dbp;
00264         db_pgno_t fpgno, tpgno;
00265 {
00266         DBC *dbc;
00267 
00268         /*
00269          * Adjust the cursors.  See the comment in CDB___bam_ca_delete().
00270          */
00271         MUTEX_THREAD_LOCK(dbp->mutexp);
00272         for (dbc = TAILQ_FIRST(&dbp->active_queue);
00273             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
00274                 if (dbc->dbtype == DB_RECNO)
00275                         continue;
00276                 if (dbc->internal->pgno == fpgno)
00277                         dbc->internal->pgno = tpgno;
00278         }
00279         MUTEX_THREAD_UNLOCK(dbp->mutexp);
00280 }
00281 
00282 /*
00283  * CDB___bam_ca_split --
00284  *      Adjust the cursors when splitting a page.
00285  *
00286  * PUBLIC: void CDB___bam_ca_split __P((DB *,
00287  * PUBLIC:    db_pgno_t, db_pgno_t, db_pgno_t, u_int32_t, int));
00288  */
00289 void
00290 CDB___bam_ca_split(dbp, ppgno, lpgno, rpgno, split_indx, cleft)
00291         DB *dbp;
00292         db_pgno_t ppgno, lpgno, rpgno;
00293         u_int32_t split_indx;
00294         int cleft;
00295 {
00296         DBC *dbc;
00297         DBC_INTERNAL *cp;
00298 
00299         /*
00300          * Adjust the cursors.  See the comment in CDB___bam_ca_delete().
00301          *
00302          * If splitting the page that a cursor was on, the cursor has to be
00303          * adjusted to point to the same record as before the split.  Most
00304          * of the time we don't adjust pointers to the left page, because
00305          * we're going to copy its contents back over the original page.  If
00306          * the cursor is on the right page, it is decremented by the number of
00307          * records split to the left page.
00308          */
00309         MUTEX_THREAD_LOCK(dbp->mutexp);
00310         for (dbc = TAILQ_FIRST(&dbp->active_queue);
00311             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
00312                 if (dbc->dbtype == DB_RECNO)
00313                         continue;
00314                 cp = dbc->internal;
00315                 if (cp->pgno == ppgno) {
00316                         if (cp->indx < split_indx) {
00317                                 if (cleft)
00318                                         cp->pgno = lpgno;
00319                         } else {
00320                                 cp->pgno = rpgno;
00321                                 cp->indx -= split_indx;
00322                         }
00323                 }
00324         }
00325         MUTEX_THREAD_UNLOCK(dbp->mutexp);
00326 }

Generated on Sun Jun 8 10:56:34 2008 for GNUmifluz by  doxygen 1.5.5