db2/btree/bt_recno.c

   1 /*-
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 1997
   5  *      Sleepycat Software.  All rights reserved.
   6  */
   7
   8 #include "config.h"
   9
  10 #ifndef lint
  11 static const char sccsid[] = "@(#)bt_recno.c    10.19 (Sleepycat) 9/20/97";
  12 #endif /* not lint */
  13
  14 #ifndef NO_SYSTEM_INCLUDES
  15 #include <sys/types.h>
  16
  17 #include <errno.h>
  18 #include <limits.h>
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #endif
  23
  24 #include "db_int.h"
  25 #include "db_page.h"
  26 #include "btree.h"
  27
  28 static int __ram_add __P((DB *, db_recno_t *, DBT *, int, int));
  29 static int __ram_c_close __P((DBC *));
  30 static int __ram_c_del __P((DBC *, int));
  31 static int __ram_c_get __P((DBC *, DBT *, DBT *, int));
  32 static int __ram_c_put __P((DBC *, DBT *, DBT *, int));
  33 static int __ram_fmap __P((DB *, db_recno_t));
  34 static int __ram_get __P((DB *, DB_TXN *, DBT *, DBT *, int));
  35 static int __ram_put __P((DB *, DB_TXN *, DBT *, DBT *, int));
  36 static int __ram_source __P((DB *, RECNO *, const char *));
  37 static int __ram_sync __P((DB *, int));
  38 static int __ram_update __P((DB *, db_recno_t, int));
  39 static int __ram_vmap __P((DB *, db_recno_t));
  40 static int __ram_writeback __P((DB *));
  41
  42 /*
  43  * If we're renumbering records, then we have to detect in the cursor that a
  44  * record was deleted, and adjust the cursor as necessary.  If not renumbering
  45  * records, then we can detect this by looking at the actual record, so we
  46  * ignore the cursor delete flag.
  47  */
  48 #define CD_SET(dbp, cp) {                                               \
  49         if (F_ISSET(dbp, DB_RE_RENUMBER))                               \
  50                 F_SET(cp, CR_DELETED);                                  \
  51 }
  52 #define CD_CLR(dbp, cp) {                                               \
  53         if (F_ISSET(dbp, DB_RE_RENUMBER))                               \
  54                 F_CLR(cp, CR_DELETED);                                  \
  55 }
  56 #define CD_ISSET(dbp, cp)                                               \
  57         (F_ISSET(dbp, DB_RE_RENUMBER) && F_ISSET(cp, CR_DELETED))
  58
  59 /*
  60  * __ram_open --
  61  *      Recno open function.
  62  *
  63  * PUBLIC: int __ram_open __P((DB *, DBTYPE, DB_INFO *));
  64  */
  65 int
  66 __ram_open(dbp, type, dbinfo)
  67         DB *dbp;
  68         DBTYPE type;
  69         DB_INFO *dbinfo;
  70 {
  71         BTREE *t;
  72         RECNO *rp;
  73         int ret;
  74
  75         ret = 0;
  76
  77         /* Allocate and initialize the private RECNO structure. */
  78         if ((rp = (RECNO *)calloc(1, sizeof(*rp))) == NULL)
  79                 return (ENOMEM);
  80
  81         if (dbinfo != NULL) {
  82                 /*
  83                  * If the user specified a source tree, open it and map it in.
  84                  *
  85                  * !!!
  86                  * We don't complain if the user specified transactions or
  87                  * threads.  It's possible to make it work, but you'd better
  88                  * know what you're doing!
  89                  */
  90                 if (dbinfo->re_source == NULL) {
  91                         rp->re_fd = -1;
  92                         F_SET(rp, RECNO_EOF);
  93                 } else {
  94                         if ((ret =
  95                             __ram_source(dbp, rp, dbinfo->re_source)) != 0)
  96                         goto err;
  97                 }
  98
  99                 /* Copy delimiter, length and padding values. */
 100                 rp->re_delim =
 101                     F_ISSET(dbp, DB_RE_DELIMITER) ? dbinfo->re_delim : '\n';
 102                 rp->re_pad = F_ISSET(dbp, DB_RE_PAD) ? dbinfo->re_pad : ' ';
 103
 104                 if (F_ISSET(dbp, DB_RE_FIXEDLEN)) {
 105                         if ((rp->re_len = dbinfo->re_len) == 0) {
 106                                 __db_err(dbp->dbenv,
 107                                     "record length must be greater than 0");
 108                                 ret = EINVAL;
 109                                 goto err;
 110                         }
 111                 } else
 112                         rp->re_len = 0;
 113         } else {
 114                 rp->re_delim = '\n';
 115                 rp->re_pad = ' ';
 116                 rp->re_fd = -1;
 117                 F_SET(rp, RECNO_EOF);
 118         }
 119
 120         /* Open the underlying btree. */
 121         if ((ret = __bam_open(dbp, DB_RECNO, dbinfo)) != 0)
 122                 goto err;
 123
 124         /* Set the routines necessary to make it look like a recno tree. */
 125         dbp->cursor = __ram_cursor;
 126         dbp->del = __ram_delete;
 127         dbp->get = __ram_get;
 128         dbp->put = __ram_put;
 129         dbp->sync = __ram_sync;
 130
 131         /* Link in the private recno structure. */
 132         ((BTREE *)dbp->internal)->bt_recno = rp;
 133
 134         /* If we're snapshotting an underlying source file, do it now. */
 135         if (dbinfo != NULL && F_ISSET(dbinfo, DB_SNAPSHOT))
 136                 if ((ret = __ram_snapshot(dbp)) != 0 && ret != DB_NOTFOUND)
 137                         goto err;
 138
 139         return (0);
 140
 141 err:    /* If we mmap'd a source file, discard it. */
 142         if (rp->re_smap != NULL)
 143                 (void)__db_munmap(rp->re_smap, rp->re_msize);
 144
 145         /* If we opened a source file, discard it. */
 146         if (rp->re_fd != -1)
 147                 (void)__db_close(rp->re_fd);
 148         if (rp->re_source != NULL)
 149                 FREES(rp->re_source);
 150
 151         /* If we allocated room for key/data return, discard it. */
 152         t = dbp->internal;
 153         if (t != NULL && t->bt_rkey.data != NULL)
 154                 free(t->bt_rkey.data);
 155
 156         FREE(rp, sizeof(*rp));
 157
 158         return (ret);
 159 }
 160
 161 /*
 162  * __ram_cursor --
 163  *      Recno db->cursor function.
 164  *
 165  * PUBLIC: int __ram_cursor __P((DB *, DB_TXN *, DBC **));
 166  */
 167 int
 168 __ram_cursor(dbp, txn, dbcp)
 169         DB *dbp;
 170         DB_TXN *txn;
 171         DBC **dbcp;
 172 {
 173         RCURSOR *cp;
 174         DBC *dbc;
 175
 176         DEBUG_LWRITE(dbp, txn, "ram_cursor", NULL, NULL, 0);
 177
 178         if ((dbc = (DBC *)calloc(1, sizeof(DBC))) == NULL)
 179                 return (ENOMEM);
 180         if ((cp = (RCURSOR *)calloc(1, sizeof(RCURSOR))) == NULL) {
 181                 free(dbc);
 182                 return (ENOMEM);
 183         }
 184
 185         cp->dbc = dbc;
 186         cp->recno = RECNO_OOB;
 187
 188         dbc->dbp = dbp;
 189         dbc->txn = txn;
 190         dbc->internal = cp;
 191         dbc->c_close = __ram_c_close;
 192         dbc->c_del = __ram_c_del;
 193         dbc->c_get = __ram_c_get;
 194         dbc->c_put = __ram_c_put;
 195
 196         /*
 197          * All cursors are queued from the master DB structure.  Add the
 198          * cursor to that queue.
 199          */
 200         DB_THREAD_LOCK(dbp);
 201         TAILQ_INSERT_HEAD(&dbp->curs_queue, dbc, links);
 202         DB_THREAD_UNLOCK(dbp);
 203
 204         *dbcp = dbc;
 205         return (0);
 206 }
 207
 208 /*
 209  * __ram_get --
 210  *      Recno db->get function.
 211  */
 212 static int
 213 __ram_get(argdbp, txn, key, data, flags)
 214         DB *argdbp;
 215         DB_TXN *txn;
 216         DBT *key, *data;
 217         int flags;
 218 {
 219         BTREE *t;
 220         DB *dbp;
 221         PAGE *h;
 222         db_indx_t indx;
 223         db_recno_t recno;
 224         int exact, ret, stack;
 225
 226         stack = 0;
 227
 228         DEBUG_LWRITE(argdbp, txn, "ram_get", key, NULL, flags);
 229
 230         /* Check for invalid flags. */
 231         if ((ret = __db_getchk(argdbp, key, data, flags)) != 0)
 232                 return (ret);
 233
 234         GETHANDLE(argdbp, txn, &dbp, ret);
 235         t = dbp->internal;
 236
 237         /* Check the user's record number and fill in as necessary. */
 238         if ((ret = __ram_getno(dbp, key, &recno, 0)) != 0)
 239                 goto done;
 240
 241         /* Search the tree for the record. */
 242         if ((ret = __bam_rsearch(dbp, &recno, S_FIND, 1, &exact)) != 0)
 243                 goto done;
 244         if (!exact)
 245                 return (DB_NOTFOUND);
 246         stack = 1;
 247
 248         h = t->bt_csp->page;
 249         indx = t->bt_csp->indx;
 250
 251         /* If the record has already been deleted, we couldn't have found it. */
 252         if (B_DISSET(GET_BKEYDATA(h, indx)->type)) {
 253                 ret = DB_KEYEMPTY;
 254                 goto done;
 255         }
 256
 257         /* Return the data item. */
 258         ret = __db_ret(dbp,
 259             h, indx, data, &t->bt_rdata.data, &t->bt_rdata.ulen);
 260         ++t->lstat.bt_get;
 261
 262 done:   /* Discard the stack. */
 263         if (stack)
 264                 __bam_stkrel(dbp);
 265
 266         PUTHANDLE(dbp);
 267         return (ret);
 268 }
 269
 270 /*
 271  * __ram_put --
 272  *      Recno db->put function.
 273  */
 274 static int
 275 __ram_put(argdbp, txn, key, data, flags)
 276         DB *argdbp;
 277         DB_TXN *txn;
 278         DBT *key, *data;
 279         int flags;
 280 {
 281         BTREE *t;
 282         DB *dbp;
 283         db_recno_t recno;
 284         int ret;
 285
 286         DEBUG_LWRITE(argdbp, txn, "ram_put", key, data, flags);
 287
 288         /* Check for invalid flags. */
 289         if ((ret = __db_putchk(argdbp,
 290             key, data, flags, F_ISSET(argdbp, DB_AM_RDONLY), 0)) != 0)
 291                 return (ret);
 292
 293         GETHANDLE(argdbp, txn, &dbp, ret);
 294
 295         /*
 296          * If we're appending to the tree, make sure we've read in all of
 297          * the backing source file.  Otherwise, check the user's record
 298          * number and fill in as necessary.
 299          */
 300         ret = LF_ISSET(DB_APPEND) ?
 301             __ram_snapshot(dbp) : __ram_getno(dbp, key, &recno, 1);
 302
 303         /* Add the record. */
 304         if (ret == 0)
 305                 ret = __ram_add(dbp, &recno, data, flags, 0);
 306
 307         /* If we're appending to the tree, we have to return the record. */
 308         if (ret == 0 && LF_ISSET(DB_APPEND)) {
 309                 t = dbp->internal;
 310                 ret = __db_retcopy(key, &recno, sizeof(recno),
 311                     &t->bt_rkey.data, &t->bt_rkey.ulen, dbp->db_malloc);
 312         }
 313
 314         PUTHANDLE(dbp);
 315         return (ret);
 316 }
 317
 318 /*
 319  * __ram_sync --
 320  *      Recno db->sync function.
 321  */
 322 static int
 323 __ram_sync(argdbp, flags)
 324         DB *argdbp;
 325         int flags;
 326 {
 327         DB *dbp;
 328         int ret;
 329
 330         DEBUG_LWRITE(argdbp, NULL, "ram_sync", NULL, NULL, flags);
 331
 332         /* Sync the underlying btree. */
 333         if ((ret = __bam_sync(argdbp, flags)) != 0)
 334                 return (ret);
 335
 336         /* Copy back the backing source file. */
 337         GETHANDLE(argdbp, NULL, &dbp, ret);
 338         ret = __ram_writeback(dbp);
 339         PUTHANDLE(dbp);
 340
 341         return (ret);
 342 }
 343
 344 /*
 345  * __ram_close --
 346  *      Recno db->close function.
 347  *
 348  * PUBLIC: int __ram_close __P((DB *));
 349  */
 350 int
 351 __ram_close(argdbp)
 352         DB *argdbp;
 353 {
 354         RECNO *rp;
 355
 356         DEBUG_LWRITE(argdbp, NULL, "ram_close", NULL, NULL, 0);
 357
 358         rp = ((BTREE *)argdbp->internal)->bt_recno;
 359
 360         /* Close any underlying mmap region. */
 361         if (rp->re_smap != NULL)
 362                 (void)__db_munmap(rp->re_smap, rp->re_msize);
 363
 364         /* Close any backing source file descriptor. */
 365         if (rp->re_fd != -1)
 366                 (void)__db_close(rp->re_fd);
 367
 368         /* Free any backing source file name. */
 369         if (rp->re_source != NULL)
 370                 FREES(rp->re_source);
 371
 372         /* Free allocated memory. */
 373         FREE(rp, sizeof(RECNO));
 374         ((BTREE *)argdbp->internal)->bt_recno = NULL;
 375
 376         /* Close the underlying btree. */
 377         return (__bam_close(argdbp));
 378 }
 379
 380 /*
 381  * __ram_c_close --
 382  *      Recno cursor->close function.
 383  */
 384 static int
 385 __ram_c_close(dbc)
 386         DBC *dbc;
 387 {
 388         DEBUG_LWRITE(dbc->dbp, dbc->txn, "ram_c_close", NULL, NULL, 0);
 389
 390         return (__ram_c_iclose(dbc->dbp, dbc));
 391 }
 392
 393 /*
 394  * __ram_c_iclose --
 395  *      Close a single cursor -- internal version.
 396  *
 397  * PUBLIC: int __ram_c_iclose __P((DB *, DBC *));
 398  */
 399 int
 400 __ram_c_iclose(dbp, dbc)
 401         DB *dbp;
 402         DBC *dbc;
 403 {
 404         /*
 405          * All cursors are queued from the master DB structure.  Remove the
 406          * cursor from that queue.
 407          */
 408         DB_THREAD_LOCK(dbc->dbp);
 409         TAILQ_REMOVE(&dbc->dbp->curs_queue, dbc, links);
 410         DB_THREAD_UNLOCK(dbc->dbp);
 411
 412         /* Discard the structures. */
 413         FREE(dbc->internal, sizeof(RCURSOR));
 414         FREE(dbc, sizeof(DBC));
 415
 416         return (0);
 417 }
 418
 419 /*
 420  * __ram_c_del --
 421  *      Recno cursor->c_del function.
 422  */
 423 static int
 424 __ram_c_del(dbc, flags)
 425         DBC *dbc;
 426         int flags;
 427 {
 428         DBT key;
 429         RCURSOR *cp;
 430         int ret;
 431
 432         DEBUG_LWRITE(dbc->dbp, dbc->txn, "ram_c_del", NULL, NULL, flags);
 433
 434         cp = dbc->internal;
 435
 436         /* Check for invalid flags. */
 437         if ((ret = __db_cdelchk(dbc->dbp, flags,
 438             F_ISSET(dbc->dbp, DB_AM_RDONLY), cp->recno != RECNO_OOB)) != 0)
 439                 return (ret);
 440
 441         /* If already deleted, return failure. */
 442         if (CD_ISSET(dbc->dbp, cp))
 443                 return (DB_KEYEMPTY);
 444
 445         /* Build a normal delete request. */
 446         memset(&key, 0, sizeof(key));
 447         key.data = &cp->recno;
 448         key.size = sizeof(db_recno_t);
 449         if ((ret = __ram_delete(dbc->dbp, dbc->txn, &key, 0)) == 0)
 450                 CD_SET(dbc->dbp, cp);
 451
 452         return (ret);
 453 }
 454
 455 /*
 456  * __ram_c_get --
 457  *      Recno cursor->c_get function.
 458  */
 459 static int
 460 __ram_c_get(dbc, key, data, flags)
 461         DBC *dbc;
 462         DBT *key, *data;
 463         int flags;
 464 {
 465         BTREE *t;
 466         DB *dbp;
 467         RCURSOR *cp, copy;
 468         int ret;
 469
 470         DEBUG_LREAD(dbc->dbp, dbc->txn, "ram_c_get",
 471             flags == DB_SET || flags == DB_SET_RANGE ? key : NULL,
 472             NULL, flags);
 473
 474         cp = dbc->internal;
 475         dbp = dbc->dbp;
 476
 477         /* Check for invalid flags. */
 478         if ((ret = __db_cgetchk(dbc->dbp,
 479             key, data, flags, cp->recno != RECNO_OOB)) != 0)
 480                 return (ret);
 481
 482         GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
 483         t = dbp->internal;
 484
 485         /* Initialize the cursor for a new retrieval. */
 486         copy = *cp;
 487
 488 retry:  /* Update the record number. */
 489         switch (flags) {
 490         case DB_CURRENT:
 491                 if (CD_ISSET(dbp, cp)) {
 492                         PUTHANDLE(dbp);
 493                         return (DB_KEYEMPTY);
 494                 }
 495                 break;
 496         case DB_NEXT:
 497                 if (CD_ISSET(dbp, cp))
 498                         break;
 499                 if (cp->recno != RECNO_OOB) {
 500                         ++cp->recno;
 501                         break;
 502                 }
 503                 /* FALLTHROUGH */
 504         case DB_FIRST:
 505                 flags = DB_NEXT;
 506                 cp->recno = 1;
 507                 break;
 508         case DB_PREV:
 509                 if (cp->recno != RECNO_OOB) {
 510                         if (cp->recno == 1)
 511                                 return (DB_NOTFOUND);
 512                         --cp->recno;
 513                         break;
 514                 }
 515                 /* FALLTHROUGH */
 516         case DB_LAST:
 517                 flags = DB_PREV;
 518                 if (((ret = __ram_snapshot(dbp)) != 0) && ret != DB_NOTFOUND)
 519                         goto err;
 520                 if ((ret = __bam_nrecs(dbp, &cp->recno)) != 0)
 521                         goto err;
 522                 if (cp->recno == 0)
 523                         return (DB_NOTFOUND);
 524                 break;
 525         case DB_SET:
 526         case DB_SET_RANGE:
 527                 if ((ret = __ram_getno(dbp, key, &cp->recno, 0)) != 0)
 528                         goto err;
 529                 break;
 530         }
 531
 532         /*
 533          * Return the key if the user didn't give us one, and then pass it
 534          * into __ram_get().
 535          */
 536         if (flags != DB_SET && flags != DB_SET_RANGE &&
 537             (ret = __db_retcopy(key, &cp->recno, sizeof(cp->recno),
 538             &t->bt_rkey.data, &t->bt_rkey.ulen, dbp->db_malloc)) != 0)
 539                 return (ret);
 540
 541         /*
 542          * The cursor was reset, so the delete adjustment is no
 543          * longer necessary.
 544          */
 545         CD_CLR(dbp, cp);
 546
 547         /*
 548          * Retrieve the record.
 549          *
 550          * Skip any keys that don't really exist.
 551          */
 552         if ((ret = __ram_get(dbp, dbc->txn, key, data, 0)) != 0)
 553                 if (ret == DB_KEYEMPTY &&
 554                     (flags == DB_NEXT || flags == DB_PREV))
 555                         goto retry;
 556
 557 err:    if (ret != 0)
 558                 *cp = copy;
 559
 560         PUTHANDLE(dbp);
 561         return (ret);
 562 }
 563
 564 /*
 565  * __ram_c_put --
 566  *      Recno cursor->c_put function.
 567  */
 568 static int
 569 __ram_c_put(dbc, key, data, flags)
 570         DBC *dbc;
 571         DBT *key, *data;
 572         int flags;
 573 {
 574         BTREE *t;
 575         RCURSOR *cp, copy;
 576         DB *dbp;
 577         int exact, ret;
 578         void *arg;
 579
 580         DEBUG_LWRITE(dbc->dbp, dbc->txn, "ram_c_put", NULL, data, flags);
 581
 582         cp = dbc->internal;
 583
 584         if ((ret = __db_cputchk(dbc->dbp, key, data, flags,
 585             F_ISSET(dbc->dbp, DB_AM_RDONLY), cp->recno != RECNO_OOB)) != 0)
 586                 return (ret);
 587
 588         GETHANDLE(dbc->dbp, dbc->txn, &dbp, ret);
 589         t = dbp->internal;
 590
 591         /* Initialize the cursor for a new retrieval. */
 592         copy = *cp;
 593
 594         /*
 595          * To split, we need a valid key for the page.  Since it's a cursor,
 596          * we have to build one.
 597          *
 598          * The split code discards all short-term locks and stack pages.
 599          */
 600         if (0) {
 601 split:          arg = &cp->recno;
 602                 if ((ret = __bam_split(dbp, arg)) != 0)
 603                         goto err;
 604         }
 605
 606         if ((ret = __bam_rsearch(dbp, &cp->recno, S_INSERT, 1, &exact)) != 0)
 607                 goto err;
 608         if (!exact) {
 609                 ret = DB_NOTFOUND;
 610                 goto err;
 611         }
 612         if ((ret = __bam_iitem(dbp, &t->bt_csp->page,
 613             &t->bt_csp->indx, key, data, flags, 0)) == DB_NEEDSPLIT) {
 614                 if ((ret = __bam_stkrel(dbp)) != 0)
 615                         goto err;
 616                 goto split;
 617         }
 618         if ((ret = __bam_stkrel(dbp)) != 0)
 619                 goto err;
 620
 621         if (flags != DB_CURRENT) {
 622                 /* Adjust the counts. */
 623                 if ((ret = __bam_adjust(dbp, t, 1)) != 0)
 624                         goto err;
 625
 626                 switch (flags) {
 627                 case DB_AFTER:
 628                         /* Adjust the cursors. */
 629                         __ram_ca(dbp, cp->recno, CA_IAFTER);
 630
 631                         /* Set this cursor to reference the new record. */
 632                         cp->recno = copy.recno + 1;
 633                         break;
 634                 case DB_BEFORE:
 635                         /* Adjust the cursors. */
 636                         __ram_ca(dbp, cp->recno, CA_IBEFORE);
 637
 638                         /* Set this cursor to reference the new record. */
 639                         cp->recno = copy.recno;
 640                         break;
 641                 }
 642
 643         }
 644
 645         /*
 646          * The cursor was reset, so the delete adjustment is no
 647          * longer necessary.
 648          */
 649         CD_CLR(dbp, cp);
 650
 651 err:    if (ret != 0)
 652                 *cp = copy;
 653
 654         PUTHANDLE(dbp);
 655         return (ret);
 656 }
 657
 658 /*
 659  * __ram_ca --
 660  *      Adjust cursors.
 661  *
 662  * PUBLIC: void __ram_ca __P((DB *, db_recno_t, ca_recno_arg));
 663  */
 664 void
 665 __ram_ca(dbp, recno, op)
 666         DB *dbp;
 667         db_recno_t recno;
 668         ca_recno_arg op;
 669 {
 670         DBC *dbc;
 671         RCURSOR *cp;
 672
 673         /*
 674          * Adjust the cursors.  See the comment in __bam_ca_delete().
 675          */
 676         DB_THREAD_LOCK(dbp);
 677         for (dbc = TAILQ_FIRST(&dbp->curs_queue);
 678             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
 679                 cp = (RCURSOR *)dbc->internal;
 680                 switch (op) {
 681                 case CA_DELETE:
 682                         if (recno > cp->recno)
 683                                 --cp->recno;
 684                         break;
 685                 case CA_IAFTER:
 686                         if (recno > cp->recno)
 687                                 ++cp->recno;
 688                         break;
 689                 case CA_IBEFORE:
 690                         if (recno >= cp->recno)
 691                                 ++cp->recno;
 692                         break;
 693                 }
 694         }
 695         DB_THREAD_UNLOCK(dbp);
 696 }
 697
 698 #ifdef DEBUG
 699 /*
 700  * __ram_cprint --
 701  *      Display the current recno cursor list.
 702  */
 703 int
 704 __ram_cprint(dbp)
 705         DB *dbp;
 706 {
 707         DBC *dbc;
 708         RCURSOR *cp;
 709
 710         DB_THREAD_LOCK(dbp);
 711         for (dbc = TAILQ_FIRST(&dbp->curs_queue);
 712             dbc != NULL; dbc = TAILQ_NEXT(dbc, links)) {
 713                 cp = (RCURSOR *)dbc->internal;
 714                 fprintf(stderr,
 715                     "%#0x: recno: %lu\n", (u_int)cp, (u_long)cp->recno);
 716         }
 717         DB_THREAD_UNLOCK(dbp);
 718         return (0);
 719 }
 720 #endif /* DEBUG */
 721
 722 /*
 723  * __ram_getno --
 724  *      Check the user's record number, and make sure we've seen it.
 725  *
 726  * PUBLIC: int __ram_getno __P((DB *, const DBT *, db_recno_t *, int));
 727  */
 728 int
 729 __ram_getno(dbp, key, rep, can_create)
 730         DB *dbp;
 731         const DBT *key;
 732         db_recno_t *rep;
 733         int can_create;
 734 {
 735         db_recno_t recno;
 736
 737         /* Check the user's record number. */
 738         if ((recno = *(db_recno_t *)key->data) == 0) {
 739                 __db_err(dbp->dbenv, "illegal record number of 0");
 740                 return (EINVAL);
 741         }
 742         if (rep != NULL)
 743                 *rep = recno;
 744
 745         /*
 746          * Btree can neither create records or read them in.  Recno can
 747          * do both, see if we can find the record.
 748          */
 749         return (dbp->type == DB_RECNO ?
 750             __ram_update(dbp, recno, can_create) : 0);
 751 }
 752
 753 /*
 754  * __ram_snapshot --
 755  *      Read in any remaining records from the backing input file.
 756  *
 757  * PUBLIC: int __ram_snapshot __P((DB *));
 758  */
 759 int
 760 __ram_snapshot(dbp)
 761         DB *dbp;
 762 {
 763         return (__ram_update(dbp, DB_MAX_RECORDS, 0));
 764 }
 765
 766 /*
 767  * __ram_update --
 768  *      Ensure the tree has records up to and including the specified one.
 769  */
 770 static int
 771 __ram_update(dbp, recno, can_create)
 772         DB *dbp;
 773         db_recno_t recno;
 774         int can_create;
 775 {
 776         BTREE *t;
 777         RECNO *rp;
 778         db_recno_t nrecs;
 779         int ret;
 780
 781         t = dbp->internal;
 782         rp = t->bt_recno;
 783
 784         /*
 785          * If we can't create records and we've read the entire backing input
 786          * file, we're done.
 787          */
 788         if (!can_create && F_ISSET(rp, RECNO_EOF))
 789                 return (0);
 790
 791         /*
 792          * If we haven't seen this record yet, try to get it from the original
 793          * file.
 794          */
 795         if ((ret = __bam_nrecs(dbp, &nrecs)) != 0)
 796                 return (ret);
 797         if (!F_ISSET(rp, RECNO_EOF) && recno > nrecs) {
 798                 if ((ret = rp->re_irec(dbp, recno)) != 0)
 799                         return (ret);
 800                 if ((ret = __bam_nrecs(dbp, &nrecs)) != 0)
 801                         return (ret);
 802         }
 803
 804         /*
 805          * If we can create records, create empty ones up to the requested
 806          * record.
 807          */
 808         if (!can_create || recno <= nrecs + 1)
 809                 return (0);
 810
 811         t->bt_rdata.dlen = 0;
 812         t->bt_rdata.doff = 0;
 813         t->bt_rdata.flags = 0;
 814         if (F_ISSET(dbp, DB_RE_FIXEDLEN)) {
 815                 if (t->bt_rdata.ulen < rp->re_len) {
 816                         t->bt_rdata.data = t->bt_rdata.data == NULL ?
 817                             (void *)malloc(rp->re_len) :
 818                             (void *)realloc(t->bt_rdata.data, rp->re_len);
 819                         if (t->bt_rdata.data == NULL) {
 820                                 t->bt_rdata.ulen = 0;
 821                                 return (ENOMEM);
 822                         }
 823                         t->bt_rdata.ulen = rp->re_len;
 824                 }
 825                 t->bt_rdata.size = rp->re_len;
 826                 memset(t->bt_rdata.data, rp->re_pad, rp->re_len);
 827         } else
 828                 t->bt_rdata.size = 0;
 829
 830         while (recno > ++nrecs)
 831                 if ((ret = __ram_add(dbp,
 832                     &nrecs, &t->bt_rdata, 0, BI_DELETED)) != 0)
 833                         return (ret);
 834         return (0);
 835 }
 836
 837 /*
 838  * __ram_source --
 839  *      Load information about the backing file.
 840  */
 841 static int
 842 __ram_source(dbp, rp, fname)
 843         DB *dbp;
 844         RECNO *rp;
 845         const char *fname;
 846 {
 847         off_t size;
 848         int oflags, ret;
 849
 850         if ((ret = __db_appname(dbp->dbenv,
 851             DB_APP_DATA, NULL, fname, NULL, &rp->re_source)) != 0)
 852                 return (ret);
 853
 854         oflags = F_ISSET(dbp, DB_AM_RDONLY) ? DB_RDONLY : 0;
 855         if ((ret =
 856             __db_fdopen(rp->re_source, oflags, oflags, 0, &rp->re_fd)) != 0) {
 857                 __db_err(dbp->dbenv, "%s: %s", rp->re_source, strerror(ret));
 858                 goto err;
 859         }
 860
 861         /*
 862          * XXX
 863          * We'd like to test to see if the file is too big to mmap.  Since we
 864          * don't know what size or type off_t's or size_t's are, or the largest
 865          * unsigned integral type is, or what random insanity the local C
 866          * compiler will perpetrate, doing the comparison in a portable way is
 867          * flatly impossible.  Hope that mmap fails if the file is too large.
 868          */
 869         if ((ret =
 870             __db_stat(dbp->dbenv, rp->re_source, rp->re_fd, &size, NULL)) != 0)
 871                 goto err;
 872         if (size == 0) {
 873                 F_SET(rp, RECNO_EOF);
 874                 return (0);
 875         }
 876
 877         if ((ret = __db_mmap(rp->re_fd, (size_t)size, 1, 1, &rp->re_smap)) != 0)
 878                 goto err;
 879         rp->re_cmap = rp->re_smap;
 880         rp->re_emap = (u_int8_t *)rp->re_smap + (rp->re_msize = size);
 881         rp->re_irec = F_ISSET(dbp, DB_RE_FIXEDLEN) ?  __ram_fmap : __ram_vmap;
 882         return (0);
 883
 884 err:    FREES(rp->re_source)
 885         return (ret);
 886 }
 887
 888 /*
 889  * __ram_writeback --
 890  *      Rewrite the backing file.
 891  */
 892 static int
 893 __ram_writeback(dbp)
 894         DB *dbp;
 895 {
 896         RECNO *rp;
 897         DBT key, data;
 898         db_recno_t keyno;
 899         ssize_t nw;
 900         int fd, ret, t_ret;
 901         u_int8_t delim, *pad;
 902
 903         rp = ((BTREE *)dbp->internal)->bt_recno;
 904
 905         /* If the file wasn't modified, we're done. */
 906         if (!F_ISSET(rp, RECNO_MODIFIED))
 907                 return (0);
 908
 909         /* If there's no backing source file, we're done. */
 910         if (rp->re_source == NULL) {
 911                 F_CLR(rp, RECNO_MODIFIED);
 912                 return (0);
 913         }
 914
 915         /*
 916          * Read any remaining records into the tree.
 917          *
 918          * XXX
 919          * This is why we can't support transactions when applications specify
 920          * backing (re_source) files.  At this point we have to read in the
 921          * rest of the records from the file so that we can write all of the
 922          * records back out again, which could modify a page for which we'd
 923          * have to log changes and which we don't have locked.  This could be
 924          * partially fixed by taking a snapshot of the entire file during the
 925          * db_open(), or, since db_open() isn't transaction protected, as part
 926          * of the first DB operation.  But, if a checkpoint occurs then, the
 927          * part of the log holding the copy of the file could be discarded, and
 928          * that would make it impossible to recover in the face of disaster.
 929          * This could all probably be fixed, but it would require transaction
 930          * protecting the backing source file, i.e. mpool would have to know
 931          * about it, and we don't want to go there.
 932          */
 933         if ((ret = __ram_snapshot(dbp)) != 0 && ret != DB_NOTFOUND)
 934                 return (ret);
 935
 936         /*
 937          * !!!
 938          * Close any underlying mmap region.  This is required for Windows NT
 939          * (4.0, Service Pack 2) -- if the file is still mapped, the following
 940          * open will fail.
 941          */
 942         if (rp->re_smap != NULL) {
 943                 (void)__db_munmap(rp->re_smap, rp->re_msize);
 944                 rp->re_smap = NULL;
 945         }
 946
 947         /* Get rid of any backing file descriptor, just on GP's. */
 948         if (rp->re_fd != -1) {
 949                 (void)__db_close(rp->re_fd);
 950                 rp->re_fd = -1;
 951         }
 952
 953         /* Open the file, truncating it. */
 954         if ((ret = __db_fdopen(rp->re_source,
 955             DB_SEQUENTIAL | DB_TRUNCATE,
 956             DB_SEQUENTIAL | DB_TRUNCATE, 0, &fd)) != 0) {
 957                 __db_err(dbp->dbenv, "%s: %s", rp->re_source, strerror(ret));
 958                 return (ret);
 959         }
 960
 961         /*
 962          * We step through the records, writing each one out.  Use the record
 963          * number and the dbp->get() function, instead of a cursor, so we find
 964          * and write out "deleted" or non-existent records.
 965          */
 966         memset(&key, 0, sizeof(key));
 967         memset(&data, 0, sizeof(data));
 968         key.size = sizeof(db_recno_t);
 969         key.data = &keyno;
 970
 971         /*
 972          * We'll need the delimiter if we're doing variable-length records,
 973          * and the pad character if we're doing fixed-length records.
 974          */
 975         delim = rp->re_delim;
 976         if (F_ISSET(dbp, DB_RE_FIXEDLEN)) {
 977                 if ((pad = malloc(rp->re_len)) == NULL) {
 978                         ret = ENOMEM;
 979                         goto err;
 980                 }
 981                 memset(pad, rp->re_pad, rp->re_len);
 982         } else
 983                 pad = NULL;                     /* XXX: Shut the compiler up. */
 984         for (keyno = 1;; ++keyno) {
 985                 switch (ret = dbp->get(dbp, NULL, &key, &data, 0)) {
 986                 case 0:
 987                         if ((ret =
 988                             __db_write(fd, data.data, data.size, &nw)) != 0)
 989                                 goto err;
 990                         if (nw != (ssize_t)data.size) {
 991                                 ret = EIO;
 992                                 goto err;
 993                         }
 994                         break;
 995                 case DB_KEYEMPTY:
 996                         if (F_ISSET(dbp, DB_RE_FIXEDLEN)) {
 997                                 if ((ret =
 998                                     __db_write(fd, pad, rp->re_len, &nw)) != 0)
 999                                         goto err;
1000                                 if (nw != (ssize_t)rp->re_len) {
1001                                         ret = EIO;
1002                                         goto err;
1003                                 }
1004                         }
1005                         break;
1006                 case DB_NOTFOUND:
1007                         ret = 0;
1008                         goto done;
1009                 }
1010                 if (!F_ISSET(dbp, DB_RE_FIXEDLEN)) {
1011                         if ((ret = __db_write(fd, &delim, 1, &nw)) != 0)
1012                                 goto err;
1013                         if (nw != 1) {
1014                                 ret = EIO;
1015                                 goto err;
1016                         }
1017                 }
1018         }
1019
1020 err:
1021 done:   /* Close the file descriptor. */
1022         if ((t_ret = __db_close(fd)) != 0 || ret == 0)
1023                 ret = t_ret;
1024
1025         if (ret == 0)
1026                 F_CLR(rp, RECNO_MODIFIED);
1027         return (ret);
1028 }
1029
1030 /*
1031  * __ram_fmap --
1032  *      Get fixed length records from a file.
1033  */
1034 static int
1035 __ram_fmap(dbp, top)
1036         DB *dbp;
1037         db_recno_t top;
1038 {
1039         BTREE *t;
1040         DBT data;
1041         RECNO *rp;
1042         db_recno_t recno;
1043         u_int32_t len;
1044         u_int8_t *sp, *ep, *p;
1045         int ret;
1046
1047         if ((ret = __bam_nrecs(dbp, &recno)) != 0)
1048                 return (ret);
1049
1050         t = dbp->internal;
1051         rp = t->bt_recno;
1052         if (t->bt_rdata.ulen < rp->re_len) {
1053                 t->bt_rdata.data = t->bt_rdata.data == NULL ?
1054                     (void *)malloc(rp->re_len) :
1055                     (void *)realloc(t->bt_rdata.data, rp->re_len);
1056                 if (t->bt_rdata.data == NULL) {
1057                         t->bt_rdata.ulen = 0;
1058                         return (ENOMEM);
1059                 }
1060                 t->bt_rdata.ulen = rp->re_len;
1061         }
1062
1063         memset(&data, 0, sizeof(data));
1064         data.data = t->bt_rdata.data;
1065         data.size = rp->re_len;
1066
1067         sp = (u_int8_t *)rp->re_cmap;
1068         ep = (u_int8_t *)rp->re_emap;
1069         while (recno <= top) {
1070                 if (sp >= ep) {
1071                         F_SET(rp, RECNO_EOF);
1072                         return (DB_NOTFOUND);
1073                 }
1074                 len = rp->re_len;
1075                 for (p = t->bt_rdata.data;
1076                     sp < ep && len > 0; *p++ = *sp++, --len);
1077
1078                 /*
1079                  * Another process may have read some portion of the input
1080                  * file already, in which case we just want to discard the
1081                  * new record.
1082                  *
1083                  * XXX
1084                  * We should just do a seek, since the records are fixed
1085                  * length.
1086                  */
1087                 if (rp->re_last >= recno) {
1088                         if (len != 0)
1089                                 memset(p, rp->re_pad, len);
1090
1091                         ++recno;
1092                         if ((ret = __ram_add(dbp, &recno, &data, 0, 0)) != 0)
1093                                 return (ret);
1094                 }
1095                 ++rp->re_last;
1096         }
1097         rp->re_cmap = sp;
1098         return (0);
1099 }
1100
1101 /*
1102  * __ram_vmap --
1103  *      Get variable length records from a file.
1104  */
1105 static int
1106 __ram_vmap(dbp, top)
1107         DB *dbp;
1108         db_recno_t top;
1109 {
1110         BTREE *t;
1111         DBT data;
1112         RECNO *rp;
1113         db_recno_t recno;
1114         u_int8_t *sp, *ep;
1115         int delim, ret;
1116
1117         t = dbp->internal;
1118         rp = t->bt_recno;
1119
1120         if ((ret = __bam_nrecs(dbp, &recno)) != 0)
1121                 return (ret);
1122
1123         memset(&data, 0, sizeof(data));
1124
1125         delim = rp->re_delim;
1126
1127         sp = (u_int8_t *)rp->re_cmap;
1128         ep = (u_int8_t *)rp->re_emap;
1129         while (recno <= top) {
1130                 if (sp >= ep) {
1131                         F_SET(rp, RECNO_EOF);
1132                         return (DB_NOTFOUND);
1133                 }
1134                 for (data.data = sp; sp < ep && *sp != delim; ++sp);
1135
1136                 /*
1137                  * Another process may have read some portion of the input
1138                  * file already, in which case we just want to discard the
1139                  * new record.
1140                  */
1141                 if (rp->re_last >= recno) {
1142                         data.size = sp - (u_int8_t *)data.data;
1143                         ++recno;
1144                         if ((ret = __ram_add(dbp, &recno, &data, 0, 0)) != 0)
1145                                 return (ret);
1146                 }
1147                 ++rp->re_last;
1148                 ++sp;
1149         }
1150         rp->re_cmap = sp;
1151         return (0);
1152 }
1153
1154 /*
1155  * __ram_add --
1156  *      Add records into the tree.
1157  */
1158 static int
1159 __ram_add(dbp, recnop, data, flags, bi_flags)
1160         DB *dbp;
1161         db_recno_t *recnop;
1162         DBT *data;
1163         int flags, bi_flags;
1164 {
1165         BTREE *t;
1166         PAGE *h;
1167         db_indx_t indx;
1168         int exact, ret, stack;
1169
1170         t = dbp->internal;
1171
1172 retry:  /* Find the slot for insertion. */
1173         if ((ret = __bam_rsearch(dbp, recnop,
1174             S_INSERT | (LF_ISSET(DB_APPEND) ? S_APPEND : 0), 1, &exact)) != 0)
1175                 return (ret);
1176         h = t->bt_csp->page;
1177         indx = t->bt_csp->indx;
1178         stack = 1;
1179
1180         /*
1181          * The recno access method doesn't currently support duplicates, so
1182          * if an identical key is already in the tree we're either overwriting
1183          * it or an error is returned.
1184          */
1185         if (exact && LF_ISSET(DB_NOOVERWRITE)) {
1186                 ret = DB_KEYEXIST;
1187                 goto err;
1188         }
1189
1190         /*
1191          * Select the arguments for __bam_iitem() and do the insert.  If the
1192          * key is an exact match, or we're replacing the data item with a
1193          * new data item.  If the key isn't an exact match, we're inserting
1194          * a new key/data pair, before the search location.
1195          */
1196         if ((ret = __bam_iitem(dbp, &h, &indx, NULL,
1197             data, exact ? DB_CURRENT : DB_BEFORE, bi_flags)) == DB_NEEDSPLIT) {
1198                 (void)__bam_stkrel(dbp);
1199                 stack = 0;
1200                 if ((ret = __bam_split(dbp, recnop)) != 0)
1201                         goto err;
1202                 goto retry;
1203         }
1204
1205         if (!exact && ret == 0)
1206                 __bam_adjust(dbp, t, 1);
1207
1208 err:    if (stack)
1209                 __bam_stkrel(dbp);
1210         return (ret);
1211 }