home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / dev / gcc / ixemulsrc.lha / ixemul / db / btree / bt_open.c < prev    next >
C/C++ Source or Header  |  1996-12-11  |  11KB  |  447 lines
  1. /*    $NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $    */
  2.  
  3. /*-
  4.  * Copyright (c) 1990, 1993, 1994
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Mike Olson.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #if defined(LIBC_SCCS) && !defined(lint)
  40. #if 0
  41. static char sccsid[] = "@(#)bt_open.c    8.7 (Berkeley) 6/16/94";
  42. #else
  43. static char rcsid[] = "$NetBSD: bt_open.c,v 1.7 1995/02/27 13:20:27 cgd Exp $";
  44. #endif
  45. #endif /* LIBC_SCCS and not lint */
  46.  
  47. /*
  48.  * Implementation of btree access method for 4.4BSD.
  49.  *
  50.  * The design here was originally based on that of the btree access method
  51.  * used in the Postgres database system at UC Berkeley.  This implementation
  52.  * is wholly independent of the Postgres code.
  53.  */
  54.  
  55. #include <sys/param.h>
  56. #include <sys/stat.h>
  57.  
  58. #include <errno.h>
  59. #include <fcntl.h>
  60. #include <limits.h>
  61. #include <signal.h>
  62. #include <stdio.h>
  63. #include <stdlib.h>
  64. #include <string.h>
  65. #include <unistd.h>
  66.  
  67. #include <db.h>
  68. #include "btree.h"
  69.  
  70. static int byteorder __P((void));
  71. static int nroot __P((BTREE *));
  72. static int tmp __P((void));
  73.  
  74. /*
  75.  * __BT_OPEN -- Open a btree.
  76.  *
  77.  * Creates and fills a DB struct, and calls the routine that actually
  78.  * opens the btree.
  79.  *
  80.  * Parameters:
  81.  *    fname:    filename (NULL for in-memory trees)
  82.  *    flags:    open flag bits
  83.  *    mode:    open permission bits
  84.  *    b:    BTREEINFO pointer
  85.  *
  86.  * Returns:
  87.  *    NULL on failure, pointer to DB on success.
  88.  *
  89.  */
  90. DB *
  91. __bt_open(fname, flags, mode, openinfo, dflags)
  92.     const char *fname;
  93.     int flags, mode, dflags;
  94.     const BTREEINFO *openinfo;
  95. {
  96.     struct stat sb;
  97.     BTMETA m;
  98.     BTREE *t;
  99.     BTREEINFO b;
  100.     DB *dbp;
  101.     pgno_t ncache;
  102.     ssize_t nr;
  103.     int machine_lorder;
  104.  
  105.     t = NULL;
  106.  
  107.     /*
  108.      * Intention is to make sure all of the user's selections are okay
  109.      * here and then use them without checking.  Can't be complete, since
  110.      * we don't know the right page size, lorder or flags until the backing
  111.      * file is opened.  Also, the file's page size can cause the cachesize
  112.      * to change.
  113.      */
  114.     machine_lorder = byteorder();
  115.     if (openinfo) {
  116.         b = *openinfo;
  117.  
  118.         /* Flags: R_DUP. */
  119.         if (b.flags & ~(R_DUP))
  120.             goto einval;
  121.  
  122.         /*
  123.          * Page size must be indx_t aligned and >= MINPSIZE.  Default
  124.          * page size is set farther on, based on the underlying file
  125.          * transfer size.
  126.          */
  127.         if (b.psize &&
  128.             (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 ||
  129.             b.psize & (sizeof(indx_t) - 1)))
  130.             goto einval;
  131.  
  132.         /* Minimum number of keys per page; absolute minimum is 2. */
  133.         if (b.minkeypage) {
  134.             if (b.minkeypage < 2)
  135.                 goto einval;
  136.         } else
  137.             b.minkeypage = DEFMINKEYPAGE;
  138.  
  139.         /* If no comparison, use default comparison and prefix. */
  140.         if (b.compare == NULL) {
  141.             b.compare = __bt_defcmp;
  142.             if (b.prefix == NULL)
  143.                 b.prefix = __bt_defpfx;
  144.         }
  145.  
  146.         if (b.lorder == 0)
  147.             b.lorder = machine_lorder;
  148.     } else {
  149.         b.compare = __bt_defcmp;
  150.         b.cachesize = 0;
  151.         b.flags = 0;
  152.         b.lorder = machine_lorder;
  153.         b.minkeypage = DEFMINKEYPAGE;
  154.         b.prefix = __bt_defpfx;
  155.         b.psize = 0;
  156.     }
  157.  
  158.     /* Check for the ubiquitous PDP-11. */
  159.     if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN)
  160.         goto einval;
  161.  
  162.     /* Allocate and initialize DB and BTREE structures. */
  163.     if ((t = (BTREE *)malloc(sizeof(BTREE))) == NULL)
  164.         goto err;
  165.     memset(t, 0, sizeof(BTREE));
  166.     t->bt_bcursor.pgno = P_INVALID;
  167.     t->bt_fd = -1;            /* Don't close unopened fd on error. */
  168.     t->bt_lorder = b.lorder;
  169.     t->bt_order = NOT;
  170.     t->bt_cmp = b.compare;
  171.     t->bt_pfx = b.prefix;
  172.     t->bt_rfd = -1;
  173.  
  174.     if ((t->bt_dbp = dbp = (DB *)malloc(sizeof(DB))) == NULL)
  175.         goto err;
  176.     t->bt_flags = 0;
  177.     if (t->bt_lorder != machine_lorder)
  178.         SET(t, B_NEEDSWAP);
  179.  
  180.     dbp->type = DB_BTREE;
  181.     dbp->internal = t;
  182.     dbp->close = __bt_close;
  183.     dbp->del = __bt_delete;
  184.     dbp->fd = __bt_fd;
  185.     dbp->get = __bt_get;
  186.     dbp->put = __bt_put;
  187.     dbp->seq = __bt_seq;
  188.     dbp->sync = __bt_sync;
  189.  
  190.     /*
  191.      * If no file name was supplied, this is an in-memory btree and we
  192.      * open a backing temporary file.  Otherwise, it's a disk-based tree.
  193.      */
  194.     if (fname) {
  195.         switch(flags & O_ACCMODE) {
  196.         case O_RDONLY:
  197.             SET(t, B_RDONLY);
  198.             break;
  199.         case O_RDWR:
  200.             break;
  201.         case O_WRONLY:
  202.         default:
  203.             goto einval;
  204.         }
  205.         
  206.         if ((t->bt_fd = open(fname, flags, mode)) < 0)
  207.             goto err;
  208.  
  209.     } else {
  210.         if ((flags & O_ACCMODE) != O_RDWR)
  211.             goto einval;
  212.         if ((t->bt_fd = tmp()) == -1)
  213.             goto err;
  214.         SET(t, B_INMEM);
  215.     }
  216.  
  217.     if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
  218.         goto err;
  219.  
  220.     if (fstat(t->bt_fd, &sb))
  221.         goto err;
  222.     if (sb.st_size) {
  223.         if ((nr = 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.m_magic == BTREEMAGIC)
  237.             CLR(t, B_NEEDSWAP);
  238.         else {
  239.             SET(t, B_NEEDSWAP);
  240.             M_32_SWAP(m.m_magic);
  241.             M_32_SWAP(m.m_version);
  242.             M_32_SWAP(m.m_psize);
  243.             M_32_SWAP(m.m_free);
  244.             M_32_SWAP(m.m_nrecs);
  245.             M_32_SWAP(m.m_flags);
  246.         }
  247.         if (m.m_magic != BTREEMAGIC || m.m_version != BTREEVERSION)
  248.             goto eftype;
  249.         if (m.m_psize < MINPSIZE || m.m_psize > MAX_PAGE_OFFSET + 1 ||
  250.             m.m_psize & (sizeof(indx_t) - 1))
  251.             goto eftype;
  252.         if (m.m_flags & ~SAVEMETA)
  253.             goto eftype;
  254.         b.psize = m.m_psize;
  255.         t->bt_flags |= m.m_flags;
  256.         t->bt_free = m.m_free;
  257.         t->bt_nrecs = m.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.             SET(t, B_NODUPS);
  274.  
  275.         t->bt_free = P_INVALID;
  276.         t->bt_nrecs = 0;
  277.         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 (!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.         SET(t, B_DB_LOCK);
  322.     if (dflags & DB_SHMEM)
  323.         SET(t, B_DB_SHMEM);
  324.     if (dflags & DB_TXN)
  325.         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 (ISSET(t, B_INMEM)) {
  442.         errno = ENOENT;
  443.         return (-1);
  444.     }
  445.     return (t->bt_fd);
  446. }
  447.