home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Berkeley DB 1.8.5a / btree / bt_open.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-24  |  11.0 KB  |  447 lines  |  [TEXT/CWIE]
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_open.c    8.10 (Berkeley) 8/17/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  * Implementation of btree access method for 4.4BSD.
  43.  *
  44.  * The design here was originally based on that of the btree access method
  45.  * used in the Postgres database system at UC Berkeley.  This implementation
  46.  * is wholly independent of the Postgres code.
  47.  */
  48.  
  49. #include <sys/param.h>
  50. #include <sys/stat.h>
  51.  
  52. #include <errno.h>
  53. #include <fcntl.h>
  54. #include <limits.h>
  55. #include <signal.h>
  56. #include <stdio.h>
  57. #include <stdlib.h>
  58. #include <string.h>
  59. #include <unistd.h>
  60.  
  61. #include <db.h>
  62. #include "btree.h"
  63.  
  64. #ifdef DEBUG
  65. #undef    MINPSIZE
  66. #define    MINPSIZE    128
  67. #endif
  68.  
  69. static int byteorder __P((void));
  70. static int nroot __P((BTREE *));
  71. static int tmp __P((void));
  72.  
  73. /*
  74.  * __BT_OPEN -- Open a btree.
  75.  *
  76.  * Creates and fills a DB struct, and calls the routine that actually
  77.  * opens the btree.
  78.  *
  79.  * Parameters:
  80.  *    fname:    filename (NULL for in-memory trees)
  81.  *    flags:    open flag bits
  82.  *    mode:    open permission bits
  83.  *    b:    BTREEINFO pointer
  84.  *
  85.  * Returns:
  86.  *    NULL on failure, pointer to DB on success.
  87.  *
  88.  */
  89. DB *
  90. __bt_open(fname, flags, mode, openinfo, dflags)
  91.     const char *fname;
  92.     int flags, mode, dflags;
  93.     const BTREEINFO *openinfo;
  94. {
  95.     struct stat sb;
  96.     BTMETA m;
  97.     BTREE *t;
  98.     BTREEINFO b;
  99.     DB *dbp;
  100.     pgno_t ncache;
  101.     ssize_t nr;
  102.     int machine_lorder;
  103.  
  104.     t = NULL;
  105.  
  106.     /*
  107.      * Intention is to make sure all of the user's selections are okay
  108.      * here and then use them without checking.  Can't be complete, since
  109.      * we don't know the right page size, lorder or flags until the backing
  110.      * file is opened.  Also, the file's page size can cause the cachesize
  111.      * to change.
  112.      */
  113.     machine_lorder = byteorder();
  114.     if (openinfo) {
  115.         b = *openinfo;
  116.  
  117.         /* Flags: R_DUP. */
  118.         if (b.flags & ~(R_DUP))
  119.             goto einval;
  120.  
  121.         /*
  122.          * Page size must be indx_t aligned and >= MINPSIZE.  Default
  123.          * page size is set farther on, based on the underlying file
  124.          * transfer size.
  125.          */
  126.         if (b.psize &&
  127.             (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
  128.             b.psize & sizeof(indx_t) - 1))
  129.             goto einval;
  130.  
  131.         /* Minimum number of keys per page; absolute minimum is 2. */
  132.         if (b.minkeypage) {
  133.             if (b.minkeypage < 2)
  134.                 goto einval;
  135.         } else
  136.             b.minkeypage = DEFMINKEYPAGE;
  137.  
  138.         /* If no comparison, use default comparison and prefix. */
  139.         if (b.compare == NULL) {
  140.             b.compare = __bt_defcmp;
  141.             if (b.prefix == NULL)
  142.                 b.prefix = __bt_defpfx;
  143.         }
  144.  
  145.         if (b.lorder == 0)
  146.             b.lorder = machine_lorder;
  147.     } else {
  148.         b.compare = __bt_defcmp;
  149.         b.cachesize = 0;
  150.         b.flags = 0;
  151.         b.lorder = machine_lorder;
  152.         b.minkeypage = DEFMINKEYPAGE;
  153.         b.prefix = __bt_defpfx;
  154.         b.psize = 0;
  155.     }
  156.  
  157.     /* Check for the ubiquitous PDP-11. */
  158.     if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
  159.         goto einval;
  160.  
  161.     /* Allocate and initialize DB and BTREE structures. */
  162.     if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL)
  163.         goto err;
  164.     memset(t, 0, sizeof(BTREE));
  165.     t->bt_fd = -1;            /* Don't close unopened fd on error. */
  166.     t->bt_lorder = b.lorder;
  167.     t->bt_order = NOT;
  168.     t->bt_cmp = b.compare;
  169.     t->bt_pfx = b.prefix;
  170.     t->bt_rfd = -1;
  171.  
  172.     if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL)
  173.         goto err;
  174.     memset(t->bt_dbp, 0, sizeof(DB));
  175.     if (t->bt_lorder != machine_lorder)
  176.         F_SET(t, B_NEEDSWAP);
  177.  
  178.     dbp->type = DB_BTREE;
  179.     dbp->internal = t;
  180.     dbp->close = __bt_close;
  181.     dbp->del = __bt_delete;
  182.     dbp->fd = __bt_fd;
  183.     dbp->get = __bt_get;
  184.     dbp->put = __bt_put;
  185.     dbp->seq = __bt_seq;
  186.     dbp->sync = __bt_sync;
  187.  
  188.     /*
  189.      * If no file name was supplied, this is an in-memory btree and we
  190.      * open a backing temporary file.  Otherwise, it's a disk-based tree.
  191.      */
  192.     if (fname) {
  193.         switch (flags & O_ACCMODE) {
  194.         case O_RDONLY:
  195.             F_SET(t, B_RDONLY);
  196.             break;
  197.         case O_RDWR:
  198.             break;
  199.         case O_WRONLY:
  200.         default:
  201.             goto einval;
  202.         }
  203.         
  204.         if ((t->bt_fd = DB_open(fname, flags, mode)) < 0)
  205.             goto err;
  206.  
  207.     } else {
  208.         if ((flags & O_ACCMODE) != O_RDWR)
  209.             goto einval;
  210.         if ((t->bt_fd = tmp()) == -1)
  211.             goto err;
  212.         F_SET(t, B_INMEM);
  213.     }
  214.  
  215. #ifndef macintosh
  216.     if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
  217.         goto err;
  218. #endif
  219.  
  220.     if (fstat(t->bt_fd, &sb))
  221.         goto err;
  222.     if (sb.st_size) {
  223.         if ((nr = DB_read(t->bt_fd, &m, sizeof(BTMETA))) < 0)
  224.             goto err;
  225.         if (nr != sizeof(BTMETA))
  226.             goto eftype;
  227.  
  228.         /*
  229.          * Read in the meta-data.  This can change the notion of what
  230.          * the lorder, page size and flags are, and, when the page size
  231.          * changes, the cachesize value can change too.  If the user
  232.          * specified the wrong byte order for an existing database, we
  233.          * don't bother to return an error, we just clear the NEEDSWAP
  234.          * bit.
  235.          */
  236.         if (m.magic == BTREEMAGIC)
  237.             F_CLR(t, B_NEEDSWAP);
  238.         else {
  239.             F_SET(t, B_NEEDSWAP);
  240.             M_32_SWAP(m.magic);
  241.             M_32_SWAP(m.version);
  242.             M_32_SWAP(m.psize);
  243.             M_32_SWAP(m.free);
  244.             M_32_SWAP(m.nrecs);
  245.             M_32_SWAP(m.flags);
  246.         }
  247.         if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
  248.             goto eftype;
  249.         if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
  250.             m.psize & sizeof(indx_t) - 1)
  251.             goto eftype;
  252.         if (m.flags & ~SAVEMETA)
  253.             goto eftype;
  254.         b.psize = m.psize;
  255.         F_SET(t, m.flags);
  256.         t->bt_free = m.free;
  257.         t->bt_nrecs = m.nrecs;
  258.     } else {
  259.         /*
  260.          * Set the page size to the best value for I/O to this file.
  261.          * Don't overflow the page offset type.
  262.          */
  263.         if (b.psize == 0) {
  264.             b.psize = sb.st_blksize;
  265.             if (b.psize < MINPSIZE)
  266.                 b.psize = MINPSIZE;
  267.             if (b.psize > MAX_PAGE_OFFSET + 1)
  268.                 b.psize = MAX_PAGE_OFFSET + 1;
  269.         }
  270.  
  271.         /* Set flag if duplicates permitted. */
  272.         if (!(b.flags & R_DUP))
  273.             F_SET(t, B_NODUPS);
  274.  
  275.         t->bt_free = P_INVALID;
  276.         t->bt_nrecs = 0;
  277.         F_SET(t, B_METADIRTY);
  278.     }
  279.  
  280.     t->bt_psize = b.psize;
  281.  
  282.     /* Set the cache size; must be a multiple of the page size. */
  283.     if (b.cachesize && b.cachesize & b.psize - 1)
  284.         b.cachesize += (~b.cachesize & b.psize - 1) + 1;
  285.     if (b.cachesize < b.psize * MINCACHE)
  286.         b.cachesize = b.psize * MINCACHE;
  287.  
  288.     /* Calculate number of pages to cache. */
  289.     ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
  290.  
  291.     /*
  292.      * The btree data structure requires that at least two keys can fit on
  293.      * a page, but other than that there's no fixed requirement.  The user
  294.      * specified a minimum number per page, and we translated that into the
  295.      * number of bytes a key/data pair can use before being placed on an
  296.      * overflow page.  This calculation includes the page header, the size
  297.      * of the index referencing the leaf item and the size of the leaf item
  298.      * structure.  Also, don't let the user specify a minkeypage such that
  299.      * a key/data pair won't fit even if both key and data are on overflow
  300.      * pages.
  301.      */
  302.     t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
  303.         (sizeof(indx_t) + NBLEAFDBT(0, 0));
  304.     if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
  305.         t->bt_ovflsize =
  306.             NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
  307.  
  308.     /* Initialize the buffer pool. */
  309.     if ((t->bt_mp =
  310.         mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
  311.         goto err;
  312.     if (!F_ISSET(t, B_INMEM))
  313.         mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
  314.  
  315.     /* Create a root page if new tree. */
  316.     if (nroot(t) == RET_ERROR)
  317.         goto err;
  318.  
  319.     /* Global flags. */
  320.     if (dflags & DB_LOCK)
  321.         F_SET(t, B_DB_LOCK);
  322.     if (dflags & DB_SHMEM)
  323.         F_SET(t, B_DB_SHMEM);
  324.     if (dflags & DB_TXN)
  325.         F_SET(t, B_DB_TXN);
  326.  
  327.     return (dbp);
  328.  
  329. einval:    errno = EINVAL;
  330.     goto err;
  331.  
  332. eftype:    errno = EFTYPE;
  333.     goto err;
  334.  
  335. err:    if (t) {
  336.         if (t->bt_dbp)
  337.             free(t->bt_dbp);
  338.         if (t->bt_fd != -1)
  339.             (void)close(t->bt_fd);
  340.         free(t);
  341.     }
  342.     return (NULL);
  343. }
  344.  
  345. /*
  346.  * NROOT -- Create the root of a new tree.
  347.  *
  348.  * Parameters:
  349.  *    t:    tree
  350.  *
  351.  * Returns:
  352.  *    RET_ERROR, RET_SUCCESS
  353.  */
  354. static int
  355. nroot(t)
  356.     BTREE *t;
  357. {
  358.     PAGE *meta, *root;
  359.     pgno_t npg;
  360.  
  361.     if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) {
  362.         mpool_put(t->bt_mp, meta, 0);
  363.         return (RET_SUCCESS);
  364.     }
  365.     if (errno != EINVAL)        /* It's OK to not exist. */
  366.         return (RET_ERROR);
  367.     errno = 0;
  368.  
  369.     if ((meta = mpool_new(t->bt_mp, &npg)) == NULL)
  370.         return (RET_ERROR);
  371.  
  372.     if ((root = mpool_new(t->bt_mp, &npg)) == NULL)
  373.         return (RET_ERROR);
  374.  
  375.     if (npg != P_ROOT)
  376.         return (RET_ERROR);
  377.     root->pgno = npg;
  378.     root->prevpg = root->nextpg = P_INVALID;
  379.     root->lower = BTDATAOFF;
  380.     root->upper = t->bt_psize;
  381.     root->flags = P_BLEAF;
  382.     memset(meta, 0, t->bt_psize);
  383.     mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
  384.     mpool_put(t->bt_mp, root, MPOOL_DIRTY);
  385.     return (RET_SUCCESS);
  386. }
  387.  
  388. static int
  389. tmp()
  390. {
  391.     sigset_t set, oset;
  392.     int fd;
  393.     char *envtmp;
  394.     char path[MAXPATHLEN];
  395.  
  396.     envtmp = getenv("TMPDIR");
  397.     (void)snprintf(path,
  398.         sizeof(path), "%s/bt.XXXXXX", envtmp ? envtmp : "/tmp");
  399.  
  400.     (void)sigfillset(&set);
  401.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  402.     if ((fd = mkstemp(path)) != -1)
  403.         (void)unlink(path);
  404.     (void)sigprocmask(SIG_SETMASK, &oset, NULL);
  405.     return(fd);
  406. }
  407.  
  408. static int
  409. byteorder()
  410. {
  411.     u_int32_t x;
  412.     u_char *p;
  413.  
  414.     x = 0x01020304;
  415.     p = (u_char *)&x;
  416.     switch (*p) {
  417.     case 1:
  418.         return (BIG_ENDIAN);
  419.     case 4:
  420.         return (LITTLE_ENDIAN);
  421.     default:
  422.         return (0);
  423.     }
  424. }
  425.  
  426. int
  427. __bt_fd(dbp)
  428.         const DB *dbp;
  429. {
  430.     BTREE *t;
  431.  
  432.     t = dbp->internal;
  433.  
  434.     /* Toss any page pinned across calls. */
  435.     if (t->bt_pinned != NULL) {
  436.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  437.         t->bt_pinned = NULL;
  438.     }
  439.  
  440.     /* In-memory database can't have a file descriptor. */
  441.     if (F_ISSET(t, B_INMEM)) {
  442.         errno = ENOENT;
  443.         return (-1);
  444.     }
  445.     return (t->bt_fd);
  446. }
  447.