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: db__dup_8c-source.html,v 1.1 2008年06月08日 10:17:27 sebdiaz Exp $"; 00012 #endif /* not lint */ 00013 00014 #ifndef NO_SYSTEM_INCLUDES 00015 #include <sys/types.h> 00016 00017 #include <string.h> 00018 #endif 00019 00020 #include "db_int.h" 00021 #include "db_page.h" 00022 #include "db_shash.h" 00023 #include "btree.h" 00024 #include "hash.h" 00025 #include "lock.h" 00026 #include "db_am.h" 00027 00028 /* 00029 * CDB___db_ditem -- 00030 * Remove an item from a page. 00031 * 00032 * PUBLIC: int CDB___db_ditem __P((DBC *, PAGE *, u_int32_t, u_int32_t)); 00033 */ 00034 int 00035 CDB___db_ditem(dbc, pagep, indx, nbytes) 00036 DBC *dbc; 00037 PAGE *pagep; 00038 u_int32_t indx, nbytes; 00039 { 00040 DB *dbp; 00041 DBT ldbt; 00042 db_indx_t cnt, offset; 00043 int ret; 00044 u_int8_t *from; 00045 00046 dbp = dbc->dbp; 00047 if (DB_LOGGING(dbc)) { 00048 ldbt.data = P_ENTRY(pagep, indx); 00049 ldbt.size = nbytes; 00050 if ((ret = CDB___db_addrem_log(dbp->dbenv, dbc->txn, 00051 &LSN(pagep), 0, DB_REM_DUP, dbp->log_fileid, PGNO(pagep), 00052 (u_int32_t)indx, nbytes, &ldbt, NULL, &LSN(pagep))) != 0) 00053 return (ret); 00054 } 00055 00056 /* 00057 * If there's only a single item on the page, we don't have to 00058 * work hard. 00059 */ 00060 if (NUM_ENT(pagep) == 1) { 00061 NUM_ENT(pagep) = 0; 00062 HOFFSET(pagep) = dbp->pgsize; 00063 return (0); 00064 } 00065 00066 /* 00067 * Pack the remaining key/data items at the end of the page. Use 00068 * memmove(3), the regions may overlap. 00069 */ 00070 from = (u_int8_t *)pagep + HOFFSET(pagep); 00071 memmove(from + nbytes, from, pagep->inp[indx] - HOFFSET(pagep)); 00072 HOFFSET(pagep) += nbytes; 00073 00074 /* Adjust the indices' offsets. */ 00075 offset = pagep->inp[indx]; 00076 for (cnt = 0; cnt < NUM_ENT(pagep); ++cnt) 00077 if (pagep->inp[cnt] < offset) 00078 pagep->inp[cnt] += nbytes; 00079 00080 /* Shift the indices down. */ 00081 --NUM_ENT(pagep); 00082 if (indx != NUM_ENT(pagep)) 00083 memmove(&pagep->inp[indx], &pagep->inp[indx + 1], 00084 sizeof(db_indx_t) * (NUM_ENT(pagep) - indx)); 00085 00086 return (0); 00087 } 00088 00089 /* 00090 * CDB___db_pitem -- 00091 * Put an item on a page. 00092 * 00093 * PUBLIC: int CDB___db_pitem 00094 * PUBLIC: __P((DBC *, PAGE *, u_int32_t, u_int32_t, DBT *, DBT *)); 00095 */ 00096 int 00097 CDB___db_pitem(dbc, pagep, indx, nbytes, hdr, data) 00098 DBC *dbc; 00099 PAGE *pagep; 00100 u_int32_t indx; 00101 u_int32_t nbytes; 00102 DBT *hdr, *data; 00103 { 00104 DB *dbp; 00105 BKEYDATA bk; 00106 DBT thdr; 00107 int ret; 00108 u_int8_t *p; 00109 00110 /* 00111 * Put a single item onto a page. The logic figuring out where to 00112 * insert and whether it fits is handled in the caller. All we do 00113 * here is manage the page shuffling. We cheat a little bit in that 00114 * we don't want to copy the dbt on a normal put twice. If hdr is 00115 * NULL, we create a BKEYDATA structure on the page, otherwise, just 00116 * copy the caller's information onto the page. 00117 * 00118 * This routine is also used to put entries onto the page where the 00119 * entry is pre-built, e.g., during recovery. In this case, the hdr 00120 * will point to the entry, and the data argument will be NULL. 00121 * 00122 * !!! 00123 * There's a tremendous potential for off-by-one errors here, since 00124 * the passed in header sizes must be adjusted for the structure's 00125 * placeholder for the trailing variable-length data field. 00126 */ 00127 dbp = dbc->dbp; 00128 if (DB_LOGGING(dbc)) 00129 if ((ret = CDB___db_addrem_log(dbp->dbenv, dbc->txn, 00130 &LSN(pagep), 0, DB_ADD_DUP, dbp->log_fileid, PGNO(pagep), 00131 (u_int32_t)indx, nbytes, hdr, data, &LSN(pagep))) != 0) 00132 return (ret); 00133 00134 if (hdr == NULL) { 00135 B_TSET(bk.type, B_KEYDATA, 0); 00136 bk.len = data == NULL ? 0 : data->size; 00137 00138 thdr.data = &bk; 00139 thdr.size = SSZA(BKEYDATA, data); 00140 hdr = &thdr; 00141 } 00142 00143 /* Adjust the index table, then put the item on the page. */ 00144 if (indx != NUM_ENT(pagep)) 00145 memmove(&pagep->inp[indx + 1], &pagep->inp[indx], 00146 sizeof(db_indx_t) * (NUM_ENT(pagep) - indx)); 00147 HOFFSET(pagep) -= nbytes; 00148 pagep->inp[indx] = HOFFSET(pagep); 00149 ++NUM_ENT(pagep); 00150 00151 p = P_ENTRY(pagep, indx); 00152 memcpy(p, hdr->data, hdr->size); 00153 if (data != NULL) 00154 memcpy(p + hdr->size, data->data, data->size); 00155 00156 return (0); 00157 } 00158 00159 /* 00160 * CDB___db_relink -- 00161 * Relink around a deleted page. 00162 * 00163 * PUBLIC: int CDB___db_relink __P((DBC *, u_int32_t, PAGE *, PAGE **, int)); 00164 */ 00165 int 00166 CDB___db_relink(dbc, add_rem, pagep, new_next, needlock) 00167 DBC *dbc; 00168 u_int32_t add_rem; 00169 PAGE *pagep, **new_next; 00170 int needlock; 00171 { 00172 DB *dbp; 00173 PAGE *np, *pp; 00174 DB_LOCK npl, ppl; 00175 DB_LSN *nlsnp, *plsnp, ret_lsn; 00176 int ret; 00177 00178 ret = 0; 00179 np = pp = NULL; 00180 npl.off = ppl.off = LOCK_INVALID; 00181 nlsnp = plsnp = NULL; 00182 dbp = dbc->dbp; 00183 00184 /* 00185 * Retrieve and lock the one/two pages. For a remove, we may need 00186 * two pages (the before and after). For an add, we only need one 00187 * because, the split took care of the prev. 00188 */ 00189 if (pagep->next_pgno != PGNO_INVALID) { 00190 if (needlock && (ret = CDB___db_lget(dbc, 00191 0, pagep->next_pgno, DB_LOCK_WRITE, 0, &npl)) != 0) 00192 goto err; 00193 if ((ret = CDB_memp_fget(dbp->mpf, 00194 &pagep->next_pgno, 0, &np)) != 0) { 00195 (void)CDB___db_pgerr(dbp, pagep->next_pgno); 00196 goto err; 00197 } 00198 nlsnp = &np->lsn; 00199 } 00200 if (add_rem == DB_REM_PAGE && pagep->prev_pgno != PGNO_INVALID) { 00201 if (needlock && (ret = CDB___db_lget(dbc, 00202 0, pagep->prev_pgno, DB_LOCK_WRITE, 0, &ppl)) != 0) 00203 goto err; 00204 if ((ret = CDB_memp_fget(dbp->mpf, 00205 &pagep->prev_pgno, 0, &pp)) != 0) { 00206 (void)CDB___db_pgerr(dbp, pagep->next_pgno); 00207 goto err; 00208 } 00209 plsnp = &pp->lsn; 00210 } 00211 00212 /* Log the change. */ 00213 if (DB_LOGGING(dbc)) { 00214 if ((ret = CDB___db_relink_log(dbp->dbenv, dbc->txn, 00215 &ret_lsn, 0, add_rem, dbp->log_fileid, 00216 pagep->pgno, &pagep->lsn, 00217 pagep->prev_pgno, plsnp, pagep->next_pgno, nlsnp)) != 0) 00218 goto err; 00219 if (np != NULL) 00220 np->lsn = ret_lsn; 00221 if (pp != NULL) 00222 pp->lsn = ret_lsn; 00223 if (add_rem == DB_REM_PAGE) 00224 pagep->lsn = ret_lsn; 00225 } 00226 00227 /* 00228 * Modify and release the two pages. 00229 * 00230 * !!! 00231 * The parameter new_next gets set to the page following the page we 00232 * are removing. If there is no following page, then new_next gets 00233 * set to NULL. 00234 */ 00235 if (np != NULL) { 00236 if (add_rem == DB_ADD_PAGE) 00237 np->prev_pgno = pagep->pgno; 00238 else 00239 np->prev_pgno = pagep->prev_pgno; 00240 if (new_next == NULL) 00241 ret = CDB_memp_fput(dbp->mpf, np, DB_MPOOL_DIRTY); 00242 else { 00243 *new_next = np; 00244 ret = CDB_memp_fset(dbp->mpf, np, DB_MPOOL_DIRTY); 00245 } 00246 if (ret != 0) 00247 goto err; 00248 if (needlock) 00249 (void)__TLPUT(dbc, npl); 00250 } else if (new_next != NULL) 00251 *new_next = NULL; 00252 00253 if (pp != NULL) { 00254 pp->next_pgno = pagep->next_pgno; 00255 if ((ret = CDB_memp_fput(dbp->mpf, pp, DB_MPOOL_DIRTY)) != 0) 00256 goto err; 00257 if (needlock) 00258 (void)__TLPUT(dbc, ppl); 00259 } 00260 return (0); 00261 00262 err: if (np != NULL) 00263 (void)CDB_memp_fput(dbp->mpf, np, 0); 00264 if (needlock && npl.off != LOCK_INVALID) 00265 (void)__TLPUT(dbc, npl); 00266 if (pp != NULL) 00267 (void)CDB_memp_fput(dbp->mpf, pp, 0); 00268 if (needlock && ppl.off != LOCK_INVALID) 00269 (void)__TLPUT(dbc, ppl); 00270 return (ret); 00271 }