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 }