home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Spezial / SPEZIAL2_97.zip / SPEZIAL2_97.iso / ANWEND / EDITOR / NVI179B / NVI179B.ZIP / db / btree / bt_open.c < prev    next >
C/C++ Source or Header  |  1997-06-29  |  13KB  |  513 lines
  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/types.h>        /* XXX: param.h may not have included types.h */
  51. #include <sys/stat.h>
  52.  
  53. #include <errno.h>
  54. #include <fcntl.h>
  55. #include <limits.h>
  56. #include <signal.h>
  57. #include <stdio.h>
  58. #include <stdlib.h>
  59. #include <string.h>
  60. #include <unistd.h>
  61.  
  62. #include <db.h>
  63. #include "btree.h"
  64.  
  65. #ifdef DEBUG
  66. #undef    MINPSIZE
  67. #define    MINPSIZE    128
  68. #endif
  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.     int nr, 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. #ifndef O_BINARY
  205. #define O_BINARY 0
  206. #endif
  207.         if ((t->bt_fd = open(fname, flags | O_BINARY, mode)) < 0)
  208.             goto err;
  209.  
  210.     } else {
  211.         if ((flags & O_ACCMODE) != O_RDWR)
  212.             goto einval;
  213.         if ((t->bt_fd = tmp()) == -1)
  214.             goto err;
  215.         F_SET(t, B_INMEM);
  216.     }
  217.  
  218.     if (fcntl(t->bt_fd, F_SETFD, 1) == -1)
  219.         goto err;
  220.  
  221.     if (fstat(t->bt_fd, &sb))
  222.         goto err;
  223.     if (sb.st_size) {
  224.         if ((nr = read(t->bt_fd, &m, sizeof(BTMETA))) < 0)
  225.             goto err;
  226.         if (nr != sizeof(BTMETA))
  227.             goto eftype;
  228.  
  229.         /*
  230.          * Read in the meta-data.  This can change the notion of what
  231.          * the lorder, page size and flags are, and, when the page size
  232.          * changes, the cachesize value can change too.  If the user
  233.          * specified the wrong byte order for an existing database, we
  234.          * don't bother to return an error, we just clear the NEEDSWAP
  235.          * bit.
  236.          */
  237.         if (m.magic == BTREEMAGIC)
  238.             F_CLR(t, B_NEEDSWAP);
  239.         else {
  240.             F_SET(t, B_NEEDSWAP);
  241.             M_32_SWAP(m.magic);
  242.             M_32_SWAP(m.version);
  243.             M_32_SWAP(m.psize);
  244.             M_32_SWAP(m.free);
  245.             M_32_SWAP(m.nrecs);
  246.             M_32_SWAP(m.flags);
  247.         }
  248.         if (m.magic != BTREEMAGIC || m.version != BTREEVERSION)
  249.             goto eftype;
  250.         if (m.psize < MINPSIZE || m.psize > MAX_PAGE_OFFSET + 1 ||
  251.             m.psize & sizeof(indx_t) - 1)
  252.             goto eftype;
  253.         if (m.flags & ~SAVEMETA)
  254.             goto eftype;
  255.         b.psize = m.psize;
  256.         F_SET(t, m.flags);
  257.         t->bt_free = m.free;
  258.         t->bt_nrecs = m.nrecs;
  259.     } else {
  260.         /*
  261.          * Set the page size to the best value for I/O to this file.
  262.          * Don't overflow the page offset type.
  263.          */
  264.         if (b.psize == 0) {
  265. #ifdef HAVE_ST_BLKSIZE
  266.             b.psize = sb.st_blksize;
  267. #else
  268.             b.psize = 4 * 1024;
  269. #endif
  270.             if (b.psize < MINPSIZE)
  271.                 b.psize = MINPSIZE;
  272.             if (b.psize > MAX_PAGE_OFFSET + 1)
  273.                 b.psize = MAX_PAGE_OFFSET + 1;
  274.         }
  275.  
  276.         /* Set flag if duplicates permitted. */
  277.         if (!(b.flags & R_DUP))
  278.             F_SET(t, B_NODUPS);
  279.  
  280.         t->bt_free = P_INVALID;
  281.         t->bt_nrecs = 0;
  282.         F_SET(t, B_METADIRTY);
  283.     }
  284.  
  285.     t->bt_psize = b.psize;
  286.  
  287.     /* Set the cache size; must be a multiple of the page size. */
  288.     if (b.cachesize && b.cachesize & b.psize - 1)
  289.         b.cachesize += (~b.cachesize & b.psize - 1) + 1;
  290.     if (b.cachesize < b.psize * MINCACHE)
  291.         b.cachesize = b.psize * MINCACHE;
  292.  
  293.     /* Calculate number of pages to cache. */
  294.     ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize;
  295.  
  296.     /*
  297.      * The btree data structure requires that at least two keys can fit on
  298.      * a page, but other than that there's no fixed requirement.  The user
  299.      * specified a minimum number per page, and we translated that into the
  300.      * number of bytes a key/data pair can use before being placed on an
  301.      * overflow page.  This calculation includes the page header, the size
  302.      * of the index referencing the leaf item and the size of the leaf item
  303.      * structure.  Also, don't let the user specify a minkeypage such that
  304.      * a key/data pair won't fit even if both key and data are on overflow
  305.      * pages.
  306.      */
  307.     t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage -
  308.         (sizeof(indx_t) + NBLEAFDBT(0, 0));
  309.     if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t))
  310.         t->bt_ovflsize =
  311.             NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t);
  312.  
  313.     /* Initialize the buffer pool. */
  314.     if ((t->bt_mp =
  315.         mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL)
  316.         goto err;
  317.     if (!F_ISSET(t, B_INMEM))
  318.         mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t);
  319.  
  320.     /* Create a root page if new tree. */
  321.     if (nroot(t) == RET_ERROR)
  322.         goto err;
  323.  
  324.     /* Global flags. */
  325.     if (dflags & DB_LOCK)
  326.         F_SET(t, B_DB_LOCK);
  327.     if (dflags & DB_SHMEM)
  328.         F_SET(t, B_DB_SHMEM);
  329.     if (dflags & DB_TXN)
  330.         F_SET(t, B_DB_TXN);
  331.  
  332.     return (dbp);
  333.  
  334. einval:    errno = EINVAL;
  335.     goto err;
  336.  
  337. eftype:    errno = EFTYPE;
  338.     goto err;
  339.  
  340. err:    if (t) {
  341.         if (t->bt_dbp)
  342.             free(t->bt_dbp);
  343.         if (t->bt_fd != -1)
  344.             (void)close(t->bt_fd);
  345.         free(t);
  346.     }
  347.     return (NULL);
  348. }
  349.  
  350. /*
  351.  * NROOT -- Create the root of a new tree.
  352.  *
  353.  * Parameters:
  354.  *    t:    tree
  355.  *
  356.  * Returns:
  357.  *    RET_ERROR, RET_SUCCESS
  358.  */
  359. static int
  360. nroot(t)
  361.     BTREE *t;
  362. {
  363.     PAGE *meta, *root;
  364.     pgno_t npg;
  365.  
  366.     if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) {
  367.         mpool_put(t->bt_mp, meta, 0);
  368.         return (RET_SUCCESS);
  369.     }
  370.     if (errno != EINVAL)        /* It's OK to not exist. */
  371.         return (RET_ERROR);
  372.     errno = 0;
  373.  
  374.     if ((meta = mpool_new(t->bt_mp, &npg)) == NULL)
  375.         return (RET_ERROR);
  376.  
  377.     if ((root = mpool_new(t->bt_mp, &npg)) == NULL)
  378.         return (RET_ERROR);
  379.  
  380.     if (npg != P_ROOT)
  381.         return (RET_ERROR);
  382.     root->pgno = npg;
  383.     root->prevpg = root->nextpg = P_INVALID;
  384.     root->lower = BTDATAOFF;
  385.     root->upper = t->bt_psize;
  386.     root->flags = P_BLEAF;
  387.     memset(meta, 0, t->bt_psize);
  388.     mpool_put(t->bt_mp, meta, MPOOL_DIRTY);
  389.     mpool_put(t->bt_mp, root, MPOOL_DIRTY);
  390.     return (RET_SUCCESS);
  391. }
  392.  
  393. #ifdef VI_DOSISH
  394. struct zaplist
  395. {
  396.     char *path;
  397.     int fd;
  398.     struct zaplist *next;
  399. };
  400. static struct zaplist *zaplist;
  401.  
  402. static void
  403. bt_zapper()
  404. {
  405.     struct zaplist *zp;
  406.  
  407.     while (zaplist)
  408.     {
  409.     zp = zaplist->next;
  410.     (void) close(zaplist->fd);
  411.     (void) unlink(zaplist->path);
  412.     free(zaplist->path);
  413.     free(zaplist);
  414.     zaplist = zp;
  415.     }
  416. }
  417. #endif
  418.  
  419. static int
  420. tmp()
  421. {
  422.     sigset_t set, oset;
  423.     int fd;
  424.     char *envtmp;
  425.     char path[MAXPATHLEN];
  426.  
  427. #if VI_DOSISH
  428.     envtmp = getenv("TEMP");
  429.     if (!envtmp) envtmp = getenv("TMP");
  430. #else
  431.     envtmp = getenv("TMPDIR");
  432. #endif
  433.     (void)snprintf(path,
  434.         sizeof(path), "%s/bt.XXXXXX", envtmp ? envtmp : "/tmp");
  435.  
  436.     (void)sigfillset(&set);
  437.     (void)sigprocmask(SIG_BLOCK, &set, &oset);
  438.     if ((fd = mkstemp(path)) != -1)
  439.         (void)unlink(path);
  440. #if VI_DOSISH
  441.     else {
  442.         /* try with a shorter name */
  443.          (void)snprintf(path,
  444.             sizeof(path), "%s/btXXXXXX", envtmp ? envtmp : "/tmp");
  445.         if ((fd = mkstemp(path)) != -1)
  446.             (void)unlink(path);
  447.     }
  448.  
  449.     /*
  450.      * the backing file sticks around because you can't unlink
  451.      * an open file.  use an atexit() function and a file list.
  452.      */
  453.     {
  454.         struct zaplist *zp;
  455.  
  456.         if (fd != -1 && (zp = malloc(sizeof *zp)))
  457.         {
  458.         if (!zaplist)
  459.             atexit(bt_zapper);
  460.         zp->path = strdup(path);
  461.         zp->fd = fd;
  462.         zp->next = zaplist;
  463.         zaplist = zp;
  464.         }
  465.     }
  466. #endif
  467. #ifdef O_BINARY
  468.     if (fd != -1) setmode(fd, O_BINARY);
  469. #endif
  470.     (void)sigprocmask(SIG_SETMASK, &oset, NULL);
  471.     return(fd);
  472. }
  473.  
  474. static int
  475. byteorder()
  476. {
  477.     u_int32_t x;
  478.     u_char *p;
  479.  
  480.     x = 0x01020304;
  481.     p = (u_char *)&x;
  482.     switch (*p) {
  483.     case 1:
  484.         return (BIG_ENDIAN);
  485.     case 4:
  486.         return (LITTLE_ENDIAN);
  487.     default:
  488.         return (0);
  489.     }
  490. }
  491.  
  492. int
  493. __bt_fd(dbp)
  494.         const DB *dbp;
  495. {
  496.     BTREE *t;
  497.  
  498.     t = dbp->internal;
  499.  
  500.     /* Toss any page pinned across calls. */
  501.     if (t->bt_pinned != NULL) {
  502.         mpool_put(t->bt_mp, t->bt_pinned, 0);
  503.         t->bt_pinned = NULL;
  504.     }
  505.  
  506.     /* In-memory database can't have a file descriptor. */
  507.     if (F_ISSET(t, B_INMEM)) {
  508.         errno = ENOENT;
  509.         return (-1);
  510.     }
  511.     return (t->bt_fd);
  512. }
  513.