00001 /*- 00002 * See the file LICENSE for redistribution information. 00003 * 00004 * Copyright (c) 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__recno_8c-source.html,v 1.1 2008年06月08日 10:13:41 sebdiaz Exp $"; 00012 #endif /* not lint */ 00013 00014 #ifndef NO_SYSTEM_INCLUDES 00015 #include <sys/types.h> 00016 00017 #include <errno.h> 00018 #include <limits.h> 00019 #include <string.h> 00020 #endif 00021 00022 #include "db_int.h" 00023 #include "db_page.h" 00024 #include "btree.h" 00025 #include "db_ext.h" 00026 #include "db_shash.h" 00027 #include "lock.h" 00028 #include "lock_ext.h" 00029 #include "qam.h" 00030 00031 static int __ram_add __P((DBC *, db_recno_t *, DBT *, u_int32_t, u_int32_t)); 00032 static void __ram_ca __P((DBC *, db_recno_t, ca_recno_arg)); 00033 static int __ram_delete __P((DB *, DB_TXN *, DBT *, u_int32_t)); 00034 static int __ram_fmap __P((DBC *, db_recno_t)); 00035 static int __ram_put __P((DB *, DB_TXN *, DBT *, DBT *, u_int32_t)); 00036 static int __ram_source __P((DB *)); 00037 static int __ram_update __P((DBC *, db_recno_t, int)); 00038 static int __ram_vmap __P((DBC *, db_recno_t)); 00039 00040 /* 00041 * In recno, there are two meanings to the on-page "deleted" flag. If we're 00042 * re-numbering records, it means the record was implicitly created. We skip 00043 * over implicitly created records if doing a cursor "next" or "prev", and 00044 * return DB_KEYEMPTY if they're explicitly requested.. If not re-numbering 00045 * records, it means that the record was implicitly created, or was deleted. 00046 * We skip over implicitly created or deleted records if doing a cursor "next" 00047 * or "prev", and return DB_KEYEMPTY if they're explicitly requested. 00048 * 00049 * If we're re-numbering records, then we have to detect in the cursor that 00050 * a record was deleted, and adjust the cursor as necessary on the next get. 00051 * If we're not re-numbering records, then we can detect that a record has 00052 * been deleted by looking at the actual on-page record, so we completely 00053 * ignore the cursor's delete flag. This is different from the B+tree code. 00054 * It also maintains whether the cursor references a deleted record in the 00055 * cursor, and it doesn't always check the on-page value. 00056 */ 00057 #define CD_SET(dbp, cp) { \ 00058 if (F_ISSET(cp, C_RENUMBER)) \ 00059 F_SET(cp, C_DELETED); \ 00060 } 00061 #define CD_CLR(dbp, cp) { \ 00062 if (F_ISSET(cp, C_RENUMBER)) \ 00063 F_CLR(cp, C_DELETED); \ 00064 } 00065 #define CD_ISSET(dbp, cp) \ 00066 (F_ISSET(cp, C_RENUMBER) && F_ISSET(cp, C_DELETED)) 00067 00068 /* 00069 * CDB___ram_open -- 00070 * Recno open function. 00071 * 00072 * PUBLIC: int CDB___ram_open __P((DB *, const char *, db_pgno_t, u_int32_t)); 00073 */ 00074 int 00075 CDB___ram_open(dbp, name, base_pgno, flags) 00076 DB *dbp; 00077 const char *name; 00078 db_pgno_t base_pgno; 00079 u_int32_t flags; 00080 { 00081 BTREE *t; 00082 DBC *dbc; 00083 int ret, t_ret; 00084 00085 t = dbp->bt_internal; 00086 00087 /* Initialize the remaining fields/methods of the DB. */ 00088 dbp->del = __ram_delete; 00089 dbp->put = __ram_put; 00090 dbp->stat = CDB___bam_stat; 00091 00092 /* Start up the tree. */ 00093 if ((ret = CDB___bam_read_root(dbp, name, base_pgno, flags)) != 0) 00094 goto err; 00095 00096 /* 00097 * If the user specified a source tree, open it and map it in. 00098 * 00099 * !!! 00100 * We don't complain if the user specified transactions or threads. 00101 * It's possible to make it work, but you'd better know what you're 00102 * doing! 00103 */ 00104 if (t->re_source != NULL && (ret = __ram_source(dbp)) != 0) 00105 goto err; 00106 00107 /* If we're snapshotting an underlying source file, do it now. */ 00108 if (F_ISSET(dbp, DB_RE_SNAPSHOT)) { 00109 /* Allocate a cursor. */ 00110 if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0) 00111 goto err; 00112 00113 /* Do the snapshot. */ 00114 if ((ret = __ram_update(dbc, 00115 DB_MAX_RECORDS, 0)) != 0 && ret == DB_NOTFOUND) 00116 ret = 0; 00117 00118 /* Discard the cursor. */ 00119 if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0) 00120 ret = t_ret; 00121 00122 if (ret != 0) 00123 goto err; 00124 } 00125 00126 return (0); 00127 00128 err: /* If we mmap'd a source file, discard it. */ 00129 if (t->re_smap != NULL) 00130 (void)CDB___os_unmapfile(dbp->dbenv, t->re_smap, t->re_msize); 00131 00132 /* If we opened a source file, discard it. */ 00133 if (F_ISSET(&t->re_fh, DB_FH_VALID)) 00134 (void)CDB___os_closehandle(&t->re_fh); 00135 if (t->re_source != NULL) 00136 CDB___os_freestr(t->re_source); 00137 00138 return (ret); 00139 } 00140 00141 /* 00142 * __ram_delete -- 00143 * Recno db->del function. 00144 */ 00145 static int 00146 __ram_delete(dbp, txn, key, flags) 00147 DB *dbp; 00148 DB_TXN *txn; 00149 DBT *key; 00150 u_int32_t flags; 00151 { 00152 BTREE_CURSOR *cp; 00153 DBC *dbc; 00154 db_recno_t recno; 00155 int ret, t_ret; 00156 00157 PANIC_CHECK(dbp->dbenv); 00158 00159 /* Check for invalid flags. */ 00160 if ((ret = CDB___db_delchk(dbp, 00161 key, flags, F_ISSET(dbp, DB_AM_RDONLY))) != 0) 00162 return (ret); 00163 00164 /* Acquire a cursor. */ 00165 if ((ret = dbp->cursor(dbp, txn, &dbc, DB_WRITELOCK)) != 0) 00166 return (ret); 00167 00168 DEBUG_LWRITE(dbc, txn, "ram_delete", key, NULL, flags); 00169 00170 /* Check the user's record number and fill in as necessary. */ 00171 if ((ret = CDB___ram_getno(dbc, key, &recno, 0)) != 0) 00172 goto err; 00173 00174 /* Do the delete. */ 00175 cp = (BTREE_CURSOR *)dbc->internal; 00176 cp->recno = recno; 00177 00178 ret = CDB___ram_c_del(dbc); 00179 00180 /* Release the cursor. */ 00181 err: if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0) 00182 ret = t_ret; 00183 00184 return (ret); 00185 } 00186 00187 /* 00188 * __ram_put -- 00189 * Recno db->put function. 00190 */ 00191 static int 00192 __ram_put(dbp, txn, key, data, flags) 00193 DB *dbp; 00194 DB_TXN *txn; 00195 DBT *key, *data; 00196 u_int32_t flags; 00197 { 00198 DBC *dbc; 00199 db_recno_t recno; 00200 int ret, t_ret; 00201 00202 PANIC_CHECK(dbp->dbenv); 00203 00204 /* Check for invalid flags. */ 00205 if ((ret = CDB___db_putchk(dbp, 00206 key, data, flags, F_ISSET(dbp, DB_AM_RDONLY), 0)) != 0) 00207 return (ret); 00208 00209 /* Allocate a cursor. */ 00210 if ((ret = dbp->cursor(dbp, txn, &dbc, DB_WRITELOCK)) != 0) 00211 return (ret); 00212 00213 DEBUG_LWRITE(dbc, txn, "ram_put", key, data, flags); 00214 00215 /* 00216 * If we're appending to the tree, make sure we've read in all of 00217 * the backing source file. Otherwise, check the user's record 00218 * number and fill in as necessary. 00219 */ 00220 if (flags == DB_APPEND) { 00221 if ((ret = __ram_update( 00222 dbc, DB_MAX_RECORDS, 0)) != 0 && ret == DB_NOTFOUND) 00223 ret = 0; 00224 } else 00225 ret = CDB___ram_getno(dbc, key, &recno, 1); 00226 00227 /* Add the record. */ 00228 if (ret == 0) 00229 ret = __ram_add(dbc, &recno, data, flags, 0); 00230 00231 /* Discard the cursor. */ 00232 if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0) 00233 ret = t_ret; 00234 00235 /* Return the record number if we're appending to the tree. */ 00236 if (ret == 0 && flags == DB_APPEND) 00237 ret = CDB___db_retcopy(dbp, key, &recno, sizeof(recno), 00238 &dbc->rkey.data, &dbc->rkey.ulen); 00239 00240 return (ret); 00241 } 00242 00243 /* 00244 * CDB___ram_c_del -- 00245 * Recno cursor->c_del function. 00246 * 00247 * PUBLIC: int CDB___ram_c_del __P((DBC *)); 00248 */ 00249 int 00250 CDB___ram_c_del(dbc) 00251 DBC *dbc; 00252 { 00253 BKEYDATA bk; 00254 BTREE *t; 00255 BTREE_CURSOR *cp; 00256 DB *dbp; 00257 DBT hdr, data; 00258 EPG *epg; 00259 int exact, ret, stack; 00260 00261 dbp = dbc->dbp; 00262 cp = (BTREE_CURSOR *)dbc->internal; 00263 t = dbp->bt_internal; 00264 stack = 0; 00265 00266 /* 00267 * The semantics of cursors during delete are as follows: if record 00268 * numbers are mutable (C_RENUMBER is set), deleting a record causes 00269 * the cursor to automatically point to the immediately following 00270 * record. In this case it is possible to use a single cursor for 00271 * repeated delete operations, without intervening operations. 00272 * 00273 * If record numbers are not mutable, then records are replaced with 00274 * a marker containing a delete flag. If the record referenced by 00275 * this cursor has already been deleted, we will detect that as part 00276 * of the delete operation, and fail. 00277 */ 00278 00279 /* Search the tree for the key; delete only deletes exact matches. */ 00280 if ((ret = CDB___bam_rsearch(dbc, &cp->recno, S_DELETE, 1, &exact)) != 0) 00281 goto err; 00282 if (!exact) { 00283 ret = DB_NOTFOUND; 00284 goto err; 00285 } 00286 stack = 1; 00287 cp->page = cp->csp->page; 00288 cp->pgno = cp->csp->page->pgno; 00289 cp->indx = cp->csp->indx; 00290 00291 /* 00292 * If re-numbering records, the on-page deleted flag can only mean 00293 * that this record was implicitly created. Applications aren't 00294 * permitted to delete records they never created, return an error. 00295 * 00296 * If not re-numbering records, the on-page deleted flag means that 00297 * this record was implicitly created, or, was deleted at some time. 00298 * The former is an error because applications aren't permitted to 00299 * delete records they never created, the latter is an error because 00300 * if the record was "deleted", we could never have found it. 00301 */ 00302 if (B_DISSET(GET_BKEYDATA(cp->page, cp->indx)->type)) { 00303 ret = DB_KEYEMPTY; 00304 goto err; 00305 } 00306 00307 if (F_ISSET(cp, C_RENUMBER)) { 00308 /* Delete the item, adjust the counts, adjust the cursors. */ 00309 if ((ret = CDB___bam_ditem(dbc, cp->page, cp->indx)) != 0) 00310 goto err; 00311 CDB___bam_adjust(dbc, -1); 00312 __ram_ca(dbc, cp->recno, CA_DELETE); 00313 00314 /* 00315 * If the page is empty, delete it. 00316 * 00317 * We never delete a root page. First, root pages of primary 00318 * databases never go away, recno or otherwise. However, if 00319 * it's the root page of an off-page duplicates database, then 00320 * it can be deleted. We don't delete it here because we have 00321 * no way of telling the primary database page holder (e.g., 00322 * the hash access method) that its page element should cleaned 00323 * up because the underlying tree is gone. So, we keep the page 00324 * around until the last cursor referencing the empty tree is 00325 * are closed, and then clean it up. 00326 */ 00327 if (NUM_ENT(cp->page) == 0 && PGNO(cp->page) != cp->root) { 00328 /* 00329 * We already have a locked stack of pages. However, 00330 * there are likely entries in the stack that aren't 00331 * going to be emptied by removing the single reference 00332 * to the emptied page (or one of its parents). 00333 */ 00334 for (epg = cp->sp; epg <= cp->csp; ++epg) 00335 if (NUM_ENT(epg->page) <= 1) 00336 break; 00337 00338 /* 00339 * We want to delete a single item out of the last page 00340 * that we're not deleting, back up to that page. 00341 */ 00342 ret = CDB___bam_dpages(dbc, --epg); 00343 00344 /* 00345 * Regardless of the return from CDB___bam_dpages, it will 00346 * discard our stack and pinned page. 00347 */ 00348 stack = 0; 00349 cp->page = NULL; 00350 } 00351 } else { 00352 /* Use a delete/put pair to replace the record with a marker. */ 00353 if ((ret = CDB___bam_ditem(dbc, cp->page, cp->indx)) != 0) 00354 goto err; 00355 00356 B_TSET(bk.type, B_KEYDATA, 1); 00357 bk.len = 0; 00358 memset(&hdr, 0, sizeof(hdr)); 00359 hdr.data = &bk; 00360 hdr.size = SSZA(BKEYDATA, data); 00361 memset(&data, 0, sizeof(data)); 00362 data.data = (void *)""; 00363 data.size = 0; 00364 if ((ret = CDB___db_pitem(dbc, 00365 cp->page, cp->indx, BKEYDATA_SIZE(0), &hdr, &data)) != 0) 00366 goto err; 00367 } 00368 00369 F_SET(t, RECNO_MODIFIED); 00370 00371 err: if (stack) 00372 CDB___bam_stkrel(dbc, STK_CLRDBC); 00373 00374 return (ret); 00375 } 00376 00377 /* 00378 * CDB___ram_c_get -- 00379 * Recno cursor->c_get function. 00380 * 00381 * PUBLIC: int CDB___ram_c_get 00382 * PUBLIC: __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *)); 00383 */ 00384 int 00385 CDB___ram_c_get(dbc, key, data, flags, pgnop) 00386 DBC *dbc; 00387 DBT *key, *data; 00388 u_int32_t flags; 00389 db_pgno_t *pgnop; 00390 { 00391 BTREE_CURSOR *cp; 00392 DB *dbp; 00393 int cmp, exact, ret; 00394 00395 COMPQUIET(pgnop, NULL); 00396 00397 dbp = dbc->dbp; 00398 cp = (BTREE_CURSOR *)dbc->internal; 00399 00400 retry: switch (flags) { 00401 case DB_CURRENT: 00402 /* 00403 * If we're in a normal Recno tree with mutable record numbers, 00404 * we need make no correction if we just deleted a record, we 00405 * will return the record following the deleted one by virtue 00406 * of renumbering the tree. 00407 * 00408 * If we're in an off-page duplicate Recno tree, we are using 00409 * mutable records, but we don't implicitly move the cursor if 00410 * we delete one. 00411 */ 00412 if (F_ISSET(dbc, DBC_OPD) && F_ISSET(cp, C_DELETED)) 00413 return (DB_KEYEMPTY); 00414 break; 00415 case DB_NEXT_DUP: 00416 /* 00417 * If we're not in an off-page dup set, we know there's no 00418 * next duplicate since recnos don't have them. If we 00419 * are in an off-page dup set, the next item assuredly is 00420 * a dup, so we set flags to DB_NEXT and keep going. 00421 */ 00422 if (!F_ISSET(dbc, DBC_OPD)) 00423 return (DB_NOTFOUND); 00424 /* FALLTHROUGH */ 00425 case DB_NEXT_NODUP: 00426 /* 00427 * Recno databases don't have duplicates, set flags to DB_NEXT 00428 * and keep going. 00429 */ 00430 /* FALLTHROUGH */ 00431 case DB_NEXT: 00432 flags = DB_NEXT; 00433 /* 00434 * If record numbers are mutable: if we just deleted a record, 00435 * we have to avoid incrementing the record number so that we 00436 * return the right record by virtue of renumbering the tree. 00437 */ 00438 if (CD_ISSET(dbp, cp)) 00439 break; 00440 00441 if (cp->recno != RECNO_OOB) { 00442 ++cp->recno; 00443 break; 00444 } 00445 /* FALLTHROUGH */ 00446 case DB_FIRST: 00447 flags = DB_NEXT; 00448 cp->recno = 1; 00449 break; 00450 case DB_PREV_NODUP: 00451 /* 00452 * Recno databases don't have duplicates, set flags to DB_PREV 00453 * and keep going. 00454 */ 00455 /* FALLTHROUGH */ 00456 case DB_PREV: 00457 flags = DB_PREV; 00458 if (cp->recno != RECNO_OOB) { 00459 if (cp->recno == 1) { 00460 ret = DB_NOTFOUND; 00461 goto err; 00462 } 00463 --cp->recno; 00464 break; 00465 } 00466 /* FALLTHROUGH */ 00467 case DB_LAST: 00468 flags = DB_PREV; 00469 if (((ret = __ram_update(dbc, 00470 DB_MAX_RECORDS, 0)) != 0) && ret != DB_NOTFOUND) 00471 goto err; 00472 if ((ret = CDB___bam_nrecs(dbc, &cp->recno)) != 0) 00473 goto err; 00474 if (cp->recno == 0) { 00475 ret = DB_NOTFOUND; 00476 goto err; 00477 } 00478 break; 00479 case DB_GET_BOTHC: 00480 /* 00481 * If we're doing a join and these are offpage dups, 00482 * we want to keep searching forward from after the 00483 * current cursor position. Increment the recno by 1, 00484 * then proceed as for a DB_SET. 00485 * 00486 * Otherwise, we know there are no additional matching 00487 * data, as recnos don't have dups. return DB_NOTFOUND. 00488 */ 00489 if (F_ISSET(dbc, DBC_OPD)) { 00490 cp->recno++; 00491 break; 00492 } else 00493 ret = DB_NOTFOUND; 00494 goto err; 00495 /* NOTREACHED */ 00496 case DB_GET_BOTH: 00497 /* 00498 * If we're searching a set of off-page dups, we start 00499 * a new linear search from the first record. Otherwise, 00500 * we compare the single data item associated with the 00501 * requested record for a match. 00502 */ 00503 if (F_ISSET(dbc, DBC_OPD)) { 00504 cp->recno = 1; 00505 break; 00506 } 00507 /* FALLTHROUGH */ 00508 case DB_SET: 00509 case DB_SET_RANGE: 00510 if ((ret = CDB___ram_getno(dbc, key, &cp->recno, 0)) != 0) 00511 goto err; 00512 break; 00513 default: 00514 ret = CDB___db_unknown_flag(dbp->dbenv, "CDB___ram_c_get", flags); 00515 goto err; 00516 } 00517 00518 /* 00519 * For DB_PREV, DB_LAST, DB_SET and DB_SET_RANGE, we have already 00520 * called __ram_update() to make sure sufficient records have been 00521 * read from the backing source file. Do it now for DB_CURRENT (if 00522 * the current record was deleted we may need more records from the 00523 * backing file for a DB_CURRENT operation), DB_FIRST and DB_NEXT. 00524 */ 00525 if ((flags == DB_NEXT || flags == DB_CURRENT) && ((ret = 00526 __ram_update(dbc, cp->recno, 0)) != 0) && ret != DB_NOTFOUND) 00527 goto err; 00528 00529 for (;; ++cp->recno) { 00530 /* Search the tree for the record. */ 00531 if ((ret = CDB___bam_rsearch(dbc, &cp->recno, 00532 F_ISSET(dbc, DBC_RMW) ? S_FIND_WR : S_FIND, 00533 1, &exact)) != 0) 00534 goto err; 00535 if (!exact) { 00536 ret = DB_NOTFOUND; 00537 goto err; 00538 } 00539 00540 /* 00541 * Copy the page into the cursor, discarding any lock we 00542 * are currently holding. 00543 */ 00544 cp->page = cp->csp->page; 00545 cp->pgno = cp->csp->page->pgno; 00546 cp->indx = cp->csp->indx; 00547 (void)__TLPUT(dbc, cp->lock); 00548 cp->lock = cp->csp->lock; 00549 cp->lock_mode = cp->csp->lock_mode; 00550 00551 /* 00552 * If re-numbering records, the on-page deleted flag means this 00553 * record was implicitly created. If not re-numbering records, 00554 * the on-page deleted flag means this record was implicitly 00555 * created, or, it was deleted at some time. Regardless, we 00556 * skip such records if doing cursor next/prev operations or 00557 * walking through off-page duplicates, and fail if they were 00558 * requested explicitly by the application. 00559 */ 00560 if (B_DISSET(GET_BKEYDATA(cp->page, cp->indx)->type)) 00561 switch (flags) { 00562 case DB_NEXT: 00563 case DB_PREV: 00564 (void)CDB___bam_stkrel(dbc, STK_CLRDBC); 00565 goto retry; 00566 case DB_GET_BOTH: 00567 (void)CDB___bam_stkrel(dbc, STK_CLRDBC); 00568 continue; 00569 default: 00570 ret = DB_KEYEMPTY; 00571 goto err; 00572 } 00573 00574 if (flags == DB_GET_BOTH || flags == DB_GET_BOTHC) { 00575 if ((ret = CDB___bam_cmp(dbp, data, 00576 cp->page, cp->indx, CDB___bam_defcmp, &cmp)) != 0) 00577 return (ret); 00578 if (cmp == 0) 00579 break; 00580 if (!F_ISSET(dbc, DBC_OPD)) { 00581 ret = DB_NOTFOUND; 00582 goto err; 00583 } 00584 (void)CDB___bam_stkrel(dbc, STK_CLRDBC); 00585 } else 00586 break; 00587 } 00588 00589 /* Return the key if the user didn't give us one. */ 00590 if (!F_ISSET(dbc, DBC_OPD)) { 00591 if (flags != DB_SET && flags != DB_SET_RANGE) 00592 ret = CDB___db_retcopy(dbp, 00593 key, &cp->recno, sizeof(cp->recno), 00594 &dbc->rkey.data, &dbc->rkey.ulen); 00595 F_SET(key, DB_DBT_ISSET); 00596 } 00597 00598 /* The cursor was reset, no further delete adjustment is necessary. */ 00599 err: CD_CLR(dbp, cp); 00600 00601 return (ret); 00602 } 00603 00604 /* 00605 * CDB___ram_c_put -- 00606 * Recno cursor->c_put function. 00607 * 00608 * PUBLIC: int CDB___ram_c_put __P((DBC *, DBT *, DBT *, u_int32_t, db_pgno_t *)); 00609 */ 00610 int 00611 CDB___ram_c_put(dbc, key, data, flags, pgnop) 00612 DBC *dbc; 00613 DBT *key, *data; 00614 u_int32_t flags; 00615 db_pgno_t *pgnop; 00616 { 00617 BTREE_CURSOR *cp; 00618 DB *dbp; 00619 int exact, ret, t_ret; 00620 void *arg; 00621 00622 COMPQUIET(pgnop, NULL); 00623 00624 dbp = dbc->dbp; 00625 cp = (BTREE_CURSOR *)dbc->internal; 00626 00627 /* 00628 * DB_KEYFIRST and DB_KEYLAST will only be set if we're dealing with 00629 * an off-page duplicate tree, they can't be specified at user level. 00630 * Translate them into something else. 00631 */ 00632 switch (flags) { 00633 case DB_KEYFIRST: 00634 cp->recno = 1; 00635 flags = DB_BEFORE; 00636 break; 00637 case DB_KEYLAST: 00638 return (__ram_add(dbc, &cp->recno, data, DB_APPEND, 0)); 00639 } 00640 00641 split: if ((ret = CDB___bam_rsearch(dbc, &cp->recno, S_INSERT, 1, &exact)) != 0) 00642 goto err; 00643 if (!exact) { 00644 ret = DB_NOTFOUND; 00645 goto err; 00646 } 00647 cp->page = cp->csp->page; 00648 cp->pgno = cp->csp->page->pgno; 00649 cp->indx = cp->csp->indx; 00650 00651 ret = CDB___bam_iitem(dbc, key, data, flags, 0); 00652 t_ret = CDB___bam_stkrel(dbc, STK_CLRDBC); 00653 00654 if (t_ret != 0 && (ret == 0 || ret == DB_NEEDSPLIT)) 00655 ret = t_ret; 00656 else if (ret == DB_NEEDSPLIT) { 00657 arg = &cp->recno; 00658 if ((ret = CDB___bam_split(dbc, arg)) != 0) 00659 goto err; 00660 goto split; 00661 } 00662 if (ret != 0) 00663 goto err; 00664 00665 switch (flags) { /* Adjust the cursors. */ 00666 case DB_AFTER: 00667 __ram_ca(dbc, cp->recno, CA_IAFTER); 00668 ++cp->recno; 00669 break; 00670 case DB_BEFORE: 00671 __ram_ca(dbc, cp->recno, CA_IBEFORE); 00672 --cp->recno; 00673 break; 00674 } 00675 00676 /* Return the key if we've created a new record. */ 00677 if (!F_ISSET(dbc, DBC_OPD) && (flags == DB_AFTER || flags == DB_BEFORE)) 00678 ret = CDB___db_retcopy(dbp, key, &cp->recno, 00679 sizeof(cp->recno), &dbc->rkey.data, &dbc->rkey.ulen); 00680 00681 /* The cursor was reset, no further delete adjustment is necessary. */ 00682 err: CD_CLR(dbp, cp); 00683 00684 return (ret); 00685 } 00686 00687 /* 00688 * __ram_ca -- 00689 * Adjust cursors. 00690 */ 00691 static void 00692 __ram_ca(dbc_arg, recno, op) 00693 DBC *dbc_arg; 00694 db_recno_t recno; 00695 ca_recno_arg op; 00696 { 00697 BTREE_CURSOR *cp; 00698 DB *dbp; 00699 DBC *dbc; 00700 db_recno_t nrecs; 00701 00702 dbp = dbc_arg->dbp; 00703 00704 /* 00705 * Adjust the cursors. See the comment in CDB___bam_ca_delete(). 00706 */ 00707 MUTEX_THREAD_LOCK(dbp->mutexp); 00708 for (dbc = TAILQ_FIRST(&dbp->active_queue); 00709 dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) { 00710 cp = (BTREE_CURSOR *)dbc->internal; 00711 if (dbc_arg->internal->root != cp->root) 00712 continue; 00713 00714 switch (op) { 00715 case CA_DELETE: 00716 if (recno < cp->recno) 00717 --cp->recno; 00718 if (recno == cp->recno) { 00719 /* 00720 * If we're in an off-page duplicate Recno tree, 00721 * we are using mutable records, but we don't 00722 * implicitly move the cursor if we delete one. 00723 */ 00724 if (!F_ISSET(dbc, DBC_OPD) && 00725 CDB___bam_nrecs(dbc, &nrecs) == 0 && 00726 recno > nrecs) 00727 --cp->recno; 00728 else 00729 CD_SET(dbp, cp); 00730 } 00731 break; 00732 case CA_IAFTER: 00733 if (recno < cp->recno) 00734 ++cp->recno; 00735 break; 00736 case CA_IBEFORE: 00737 if (recno <= cp->recno) 00738 ++cp->recno; 00739 break; 00740 } 00741 } 00742 MUTEX_THREAD_UNLOCK(dbp->mutexp); 00743 } 00744 00745 /* 00746 * CDB___ram_getno -- 00747 * Check the user's record number, and make sure we've seen it. 00748 * 00749 * PUBLIC: int CDB___ram_getno __P((DBC *, const DBT *, db_recno_t *, int)); 00750 */ 00751 int 00752 CDB___ram_getno(dbc, key, rep, can_create) 00753 DBC *dbc; 00754 const DBT *key; 00755 db_recno_t *rep; 00756 int can_create; 00757 { 00758 DB *dbp; 00759 db_recno_t recno; 00760 00761 dbp = dbc->dbp; 00762 00763 /* Check the user's record number. */ 00764 if ((recno = *(db_recno_t *)key->data) == 0) { 00765 CDB___db_err(dbp->dbenv, "illegal record number of 0"); 00766 return (EINVAL); 00767 } 00768 if (rep != NULL) 00769 *rep = recno; 00770 00771 /* 00772 * Btree can neither create records nor read them in. Recno can 00773 * do both, see if we can find the record. 00774 */ 00775 return (dbc->dbtype == DB_RECNO ? 00776 __ram_update(dbc, recno, can_create) : 0); 00777 } 00778 00779 /* 00780 * __ram_update -- 00781 * Ensure the tree has records up to and including the specified one. 00782 */ 00783 static int 00784 __ram_update(dbc, recno, can_create) 00785 DBC *dbc; 00786 db_recno_t recno; 00787 int can_create; 00788 { 00789 BTREE *t; 00790 BTREE_CURSOR *cp; 00791 DB *dbp; 00792 db_recno_t nrecs; 00793 int ret; 00794 00795 dbp = dbc->dbp; 00796 cp = (BTREE_CURSOR *)dbc->internal; 00797 t = dbp->bt_internal; 00798 00799 /* 00800 * If we can't create records and we've read the entire backing input 00801 * file, we're done. 00802 */ 00803 if (!can_create && !F_ISSET(t, RECNO_READFILE)) 00804 return (0); 00805 00806 /* 00807 * If we haven't seen this record yet, try to get it from the original 00808 * file. 00809 */ 00810 if ((ret = CDB___bam_nrecs(dbc, &nrecs)) != 0) 00811 return (ret); 00812 if (F_ISSET(t, RECNO_READFILE) && recno > nrecs) { 00813 if ((ret = t->re_irec(dbc, recno)) != 0) 00814 return (ret); 00815 if ((ret = CDB___bam_nrecs(dbc, &nrecs)) != 0) 00816 return (ret); 00817 } 00818 00819 /* 00820 * If we can create records, create empty ones up to the requested 00821 * record. 00822 */ 00823 if (!can_create || recno <= nrecs + 1) 00824 return (0); 00825 00826 dbc->rdata.dlen = 0; 00827 dbc->rdata.doff = 0; 00828 dbc->rdata.flags = 0; 00829 if (F_ISSET(dbp, DB_RE_FIXEDLEN)) { 00830 if (dbc->rdata.ulen < t->re_len) { 00831 if ((ret = CDB___os_realloc(dbp->dbenv, 00832 t->re_len, NULL, &dbc->rdata.data)) != 0) { 00833 dbc->rdata.ulen = 0; 00834 dbc->rdata.data = NULL; 00835 return (ret); 00836 } 00837 dbc->rdata.ulen = t->re_len; 00838 } 00839 dbc->rdata.size = t->re_len; 00840 memset(dbc->rdata.data, t->re_pad, t->re_len); 00841 } else 00842 dbc->rdata.size = 0; 00843 00844 while (recno > ++nrecs) 00845 if ((ret = __ram_add(dbc, 00846 &nrecs, &dbc->rdata, 0, BI_DELETED)) != 0) 00847 return (ret); 00848 return (0); 00849 } 00850 00851 /* 00852 * __ram_source -- 00853 * Load information about the backing file. 00854 */ 00855 static int 00856 __ram_source(dbp) 00857 DB *dbp; 00858 { 00859 BTREE *t; 00860 size_t size; 00861 u_int32_t bytes, mbytes; 00862 char *source; 00863 int ret; 00864 00865 t = dbp->bt_internal; 00866 source = t->re_source; 00867 00868 /* 00869 * !!! 00870 * The caller has full responsibility for cleaning up on error -- 00871 * (it has to anyway, in case it fails after this routine succeeds). 00872 */ 00873 ret = CDB___db_appname(dbp->dbenv, 00874 DB_APP_DATA, NULL, source, 0, NULL, &t->re_source); 00875 00876 CDB___os_freestr(source); 00877 00878 if (ret != 0) 00879 return (ret); 00880 00881 /* 00882 * !!! 00883 * It's possible that the backing source file is read-only. We don't 00884 * much care other than we'll complain if there are any modifications 00885 * when it comes time to write the database back to the source. 00886 */ 00887 ret = CDB___os_open(dbp->dbenv, t->re_source, 00888 F_ISSET(dbp, DB_AM_RDONLY) ? DB_OSO_RDONLY : 0, 0, &t->re_fh); 00889 if (ret != 0 && !F_ISSET(dbp, DB_AM_RDONLY)) 00890 ret = CDB___os_open(dbp->dbenv, 00891 t->re_source, DB_OSO_RDONLY, 0, &t->re_fh); 00892 if (ret != 0) { 00893 CDB___db_err(dbp->dbenv, "%s: %s", t->re_source, CDB_db_strerror(ret)); 00894 return (ret); 00895 } 00896 00897 /* 00898 * !!! 00899 * We'd like to test to see if the file is too big to mmap. Since we 00900 * don't know what size or type off_t's or size_t's are, or the largest 00901 * unsigned integral type is, or what random insanity the local C 00902 * compiler will perpetrate, doing the comparison in a portable way is 00903 * flatly impossible. Hope that mmap fails if the file is too large. 00904 */ 00905 if ((ret = CDB___os_ioinfo(dbp->dbenv, t->re_source, 00906 &t->re_fh, &mbytes, &bytes, NULL)) != 0) { 00907 CDB___db_err(dbp->dbenv, "%s: %s", t->re_source, CDB_db_strerror(ret)); 00908 return (ret); 00909 } 00910 if (mbytes == 0 && bytes == 0) 00911 return (0); 00912 00913 size = mbytes * MEGABYTE + bytes; 00914 if ((ret = CDB___os_mapfile(dbp->dbenv, t->re_source, 00915 &t->re_fh, (size_t)size, 1, &t->re_smap)) != 0) 00916 return (ret); 00917 t->re_cmap = t->re_smap; 00918 t->re_emap = (u_int8_t *)t->re_smap + (t->re_msize = size); 00919 t->re_irec = F_ISSET(dbp, DB_RE_FIXEDLEN) ? __ram_fmap : __ram_vmap; 00920 F_SET(t, RECNO_READFILE); 00921 return (0); 00922 } 00923 00924 /* 00925 * CDB___ram_writeback -- 00926 * Rewrite the backing file. 00927 * 00928 * PUBLIC: int CDB___ram_writeback __P((DB *)); 00929 */ 00930 int 00931 CDB___ram_writeback(dbp) 00932 DB *dbp; 00933 { 00934 BTREE *t; 00935 DB_ENV *dbenv; 00936 DB_FH fh; 00937 DBC *dbc; 00938 DBT key, data; 00939 db_recno_t keyno; 00940 size_t nw; 00941 int ret, t_ret; 00942 u_int8_t delim, *pad; 00943 00944 t = dbp->bt_internal; 00945 dbenv = dbp->dbenv; 00946 00947 /* If the file wasn't modified, we're done. */ 00948 if (!F_ISSET(t, RECNO_MODIFIED)) 00949 return (0); 00950 00951 /* If there's no backing source file, we're done. */ 00952 if (t->re_source == NULL) { 00953 F_CLR(t, RECNO_MODIFIED); 00954 return (0); 00955 } 00956 00957 /* Allocate a cursor. */ 00958 if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0) 00959 return (ret); 00960 00961 /* 00962 * Read any remaining records into the tree. 00963 * 00964 * !!! 00965 * This is why we can't support transactions when applications specify 00966 * backing (re_source) files. At this point we have to read in the 00967 * rest of the records from the file so that we can write all of the 00968 * records back out again, which could modify a page for which we'd 00969 * have to log changes and which we don't have locked. This could be 00970 * partially fixed by taking a snapshot of the entire file during the 00971 * DB->open as DB->open is transaction protected. But, if a checkpoint 00972 * occurs then, the part of the log holding the copy of the file could 00973 * be discarded, and that would make it impossible to recover in the 00974 * face of disaster. This could all probably be fixed, but it would 00975 * require transaction protecting the backing source file, i.e. mpool 00976 * would have to know about it, and we don't want to go there. 00977 */ 00978 if ((ret = 00979 __ram_update(dbc, DB_MAX_RECORDS, 0)) != 0 && ret != DB_NOTFOUND) 00980 return (ret); 00981 00982 /* 00983 * !!! 00984 * Close any underlying mmap region. This is required for Windows NT 00985 * (4.0, Service Pack 2) -- if the file is still mapped, the following 00986 * open will fail. 00987 */ 00988 if (t->re_smap != NULL) { 00989 (void)CDB___os_unmapfile(dbenv, t->re_smap, t->re_msize); 00990 t->re_smap = NULL; 00991 } 00992 00993 /* Get rid of any backing file descriptor, just on GP's. */ 00994 if (F_ISSET(&t->re_fh, DB_FH_VALID)) 00995 (void)CDB___os_closehandle(&t->re_fh); 00996 00997 /* Open the file, truncating it. */ 00998 if ((ret = CDB___os_open(dbenv, 00999 t->re_source, DB_OSO_SEQ | DB_OSO_TRUNC, 0, &fh)) != 0) { 01000 CDB___db_err(dbenv, "%s: %s", t->re_source, CDB_db_strerror(ret)); 01001 goto err; 01002 } 01003 01004 /* 01005 * We step through the records, writing each one out. Use the record 01006 * number and the dbp->get() function, instead of a cursor, so we find 01007 * and write out "deleted" or non-existent records. 01008 */ 01009 memset(&key, 0, sizeof(key)); 01010 memset(&data, 0, sizeof(data)); 01011 key.size = sizeof(db_recno_t); 01012 key.data = &keyno; 01013 01014 /* 01015 * We'll need the delimiter if we're doing variable-length records, 01016 * and the pad character if we're doing fixed-length records. 01017 */ 01018 delim = t->re_delim; 01019 if (F_ISSET(dbp, DB_RE_FIXEDLEN)) { 01020 if ((ret = CDB___os_malloc(dbenv, t->re_len, NULL, &pad)) != 0) 01021 goto err; 01022 memset(pad, t->re_pad, t->re_len); 01023 } else 01024 COMPQUIET(pad, NULL); 01025 for (keyno = 1;; ++keyno) { 01026 switch (ret = dbp->get(dbp, NULL, &key, &data, 0)) { 01027 case 0: 01028 if ((ret = CDB___os_write(dbenv, 01029 &fh, data.data, data.size, &nw)) != 0) 01030 goto err; 01031 if (nw != (size_t)data.size) { 01032 ret = EIO; 01033 goto write_err; 01034 } 01035 break; 01036 case DB_KEYEMPTY: 01037 if (F_ISSET(dbp, DB_RE_FIXEDLEN)) { 01038 if ((ret = CDB___os_write(dbenv, 01039 &fh, pad, t->re_len, &nw)) != 0) 01040 goto write_err; 01041 if (nw != (size_t)t->re_len) { 01042 ret = EIO; 01043 goto write_err; 01044 } 01045 } 01046 break; 01047 case DB_NOTFOUND: 01048 ret = 0; 01049 goto done; 01050 } 01051 if (!F_ISSET(dbp, DB_RE_FIXEDLEN)) { 01052 if ((ret = CDB___os_write(dbenv, &fh, &delim, 1, &nw)) != 0) 01053 goto write_err; 01054 if (nw != 1) { 01055 ret = EIO; 01056 write_err: CDB___db_err(dbp->dbenv, 01057 "Write failed to backing file"); 01058 goto err; 01059 } 01060 } 01061 } 01062 01063 err: 01064 done: /* Close the file descriptor. */ 01065 if (F_ISSET(&fh, DB_FH_VALID) && 01066 (t_ret = CDB___os_closehandle(&fh)) != 0 && ret == 0) 01067 ret = t_ret; 01068 01069 /* Discard the cursor. */ 01070 if ((t_ret = dbc->c_close(dbc)) != 0 && ret == 0) 01071 ret = t_ret; 01072 01073 if (ret == 0) 01074 F_CLR(t, RECNO_MODIFIED); 01075 01076 return (ret); 01077 } 01078 01079 /* 01080 * __ram_fmap -- 01081 * Get fixed length records from a file. 01082 */ 01083 static int 01084 __ram_fmap(dbc, top) 01085 DBC *dbc; 01086 db_recno_t top; 01087 { 01088 BTREE *t; 01089 BTREE_CURSOR *cp; 01090 DB *dbp; 01091 DBT data; 01092 db_recno_t recno; 01093 u_int32_t len; 01094 u_int8_t *sp, *ep, *p; 01095 int is_modified, ret; 01096 01097 dbp = dbc->dbp; 01098 cp = (BTREE_CURSOR *)dbc->internal; 01099 t = dbp->bt_internal; 01100 01101 if ((ret = CDB___bam_nrecs(dbc, &recno)) != 0) 01102 return (ret); 01103 01104 if (dbc->rdata.ulen < t->re_len) { 01105 if ((ret = CDB___os_realloc(dbp->dbenv, 01106 t->re_len, NULL, &dbc->rdata.data)) != 0) { 01107 dbc->rdata.ulen = 0; 01108 dbc->rdata.data = NULL; 01109 return (ret); 01110 } 01111 dbc->rdata.ulen = t->re_len; 01112 } 01113 01114 is_modified = F_ISSET(t, RECNO_MODIFIED); 01115 01116 memset(&data, 0, sizeof(data)); 01117 data.data = dbc->rdata.data; 01118 data.size = t->re_len; 01119 01120 sp = (u_int8_t *)t->re_cmap; 01121 ep = (u_int8_t *)t->re_emap; 01122 while (recno < top) { 01123 if (sp >= ep) { 01124 F_CLR(t, RECNO_READFILE); 01125 ret = DB_NOTFOUND; 01126 goto err; 01127 } 01128 len = t->re_len; 01129 for (p = dbc->rdata.data; 01130 sp < ep && len > 0; *p++ = *sp++, --len) 01131 ; 01132 01133 /* 01134 * Another process may have read this record from the input 01135 * file and stored it into the database already, in which 01136 * case we don't need to repeat that operation. We detect 01137 * this by checking if the last record we've read is greater 01138 * or equal to the number of records in the database. 01139 * 01140 * XXX 01141 * We should just do a seek since the records are fixed length. 01142 */ 01143 if (t->re_last >= recno) { 01144 if (len != 0) 01145 memset(p, t->re_pad, len); 01146 01147 ++recno; 01148 if ((ret = __ram_add(dbc, &recno, &data, 0, 0)) != 0) 01149 goto err; 01150 } 01151 ++t->re_last; 01152 } 01153 t->re_cmap = sp; 01154 01155 err: if (!is_modified) 01156 F_CLR(t, RECNO_MODIFIED); 01157 01158 return (0); 01159 } 01160 01161 /* 01162 * __ram_vmap -- 01163 * Get variable length records from a file. 01164 */ 01165 static int 01166 __ram_vmap(dbc, top) 01167 DBC *dbc; 01168 db_recno_t top; 01169 { 01170 BTREE *t; 01171 DBT data; 01172 db_recno_t recno; 01173 u_int8_t *sp, *ep; 01174 int delim, is_modified, ret; 01175 01176 t = dbc->dbp->bt_internal; 01177 01178 if ((ret = CDB___bam_nrecs(dbc, &recno)) != 0) 01179 return (ret); 01180 01181 delim = t->re_delim; 01182 is_modified = F_ISSET(t, RECNO_MODIFIED); 01183 01184 memset(&data, 0, sizeof(data)); 01185 01186 sp = (u_int8_t *)t->re_cmap; 01187 ep = (u_int8_t *)t->re_emap; 01188 while (recno < top) { 01189 if (sp >= ep) { 01190 F_CLR(t, RECNO_READFILE); 01191 ret = DB_NOTFOUND; 01192 goto err; 01193 } 01194 for (data.data = sp; sp < ep && *sp != delim; ++sp) 01195 ; 01196 01197 /* 01198 * Another process may have read this record from the input 01199 * file and stored it into the database already, in which 01200 * case we don't need to repeat that operation. We detect 01201 * this by checking if the last record we've read is greater 01202 * or equal to the number of records in the database. 01203 */ 01204 if (t->re_last >= recno) { 01205 data.size = sp - (u_int8_t *)data.data; 01206 ++recno; 01207 if ((ret = __ram_add(dbc, &recno, &data, 0, 0)) != 0) 01208 goto err; 01209 } 01210 ++t->re_last; 01211 ++sp; 01212 } 01213 t->re_cmap = sp; 01214 01215 err: if (!is_modified) 01216 F_CLR(t, RECNO_MODIFIED); 01217 01218 return (ret); 01219 } 01220 01221 /* 01222 * __ram_add -- 01223 * Add records into the tree. 01224 */ 01225 static int 01226 __ram_add(dbc, recnop, data, flags, bi_flags) 01227 DBC *dbc; 01228 db_recno_t *recnop; 01229 DBT *data; 01230 u_int32_t flags, bi_flags; 01231 { 01232 BKEYDATA *bk; 01233 BTREE_CURSOR *cp; 01234 int exact, ret, stack; 01235 01236 cp = (BTREE_CURSOR *)dbc->internal; 01237 01238 retry: /* Find the slot for insertion. */ 01239 if ((ret = CDB___bam_rsearch(dbc, recnop, 01240 S_INSERT | (flags == DB_APPEND ? S_APPEND : 0), 1, &exact)) != 0) 01241 return (ret); 01242 stack = 1; 01243 cp->page = cp->csp->page; 01244 cp->pgno = cp->csp->page->pgno; 01245 cp->indx = cp->csp->indx; 01246 01247 /* 01248 * If re-numbering records, the on-page deleted flag means this record 01249 * was implicitly created. If not re-numbering records, the on-page 01250 * deleted flag means this record was implicitly created, or, it was 01251 * deleted at some time. 01252 * 01253 * If DB_NOOVERWRITE is set and the item already exists in the tree, 01254 * return an error unless the item was either marked for deletion or 01255 * only implicitly created. 01256 */ 01257 if (exact) { 01258 bk = GET_BKEYDATA(cp->page, cp->indx); 01259 if (!B_DISSET(bk->type) && flags == DB_NOOVERWRITE) { 01260 ret = DB_KEYEXIST; 01261 goto err; 01262 } 01263 } 01264 01265 /* 01266 * Select the arguments for CDB___bam_iitem() and do the insert. If the 01267 * key is an exact match, or we're replacing the data item with a 01268 * new data item, replace the current item. If the key isn't an exact 01269 * match, we're inserting a new key/data pair, before the search 01270 * location. 01271 */ 01272 switch (ret = CDB___bam_iitem(dbc, 01273 NULL, data, exact ? DB_CURRENT : DB_BEFORE, bi_flags)) { 01274 case 0: 01275 /* 01276 * Don't adjust anything. 01277 * 01278 * If we inserted a record, no cursors need adjusting because 01279 * the only new record it's possible to insert is at the very 01280 * end of the tree. The necessary adjustments to the internal 01281 * page counts were made by CDB___bam_iitem(). 01282 * 01283 * If we overwrote a record, no cursors need adjusting because 01284 * future DBcursor->get calls will simply return the underlying 01285 * record (there's no adjustment made for the DB_CURRENT flag 01286 * when a cursor get operation immediately follows a cursor 01287 * delete operation, and the normal adjustment for the DB_NEXT 01288 * flag is still correct). 01289 */ 01290 break; 01291 case DB_NEEDSPLIT: 01292 /* Discard the stack of pages and split the page. */ 01293 (void)CDB___bam_stkrel(dbc, STK_CLRDBC); 01294 stack = 0; 01295 01296 if ((ret = CDB___bam_split(dbc, recnop)) != 0) 01297 goto err; 01298 01299 goto retry; 01300 /* NOTREACHED */ 01301 default: 01302 goto err; 01303 } 01304 01305 err: if (stack) 01306 CDB___bam_stkrel(dbc, STK_CLRDBC); 01307 01308 return (ret); 01309 }