home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / dbm / src / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  28.5 KB  |  1,180 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.  * Margo Seltzer.
  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[] = "@(#)hash.c    8.9 (Berkeley) 6/16/94";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include "watcomfx.h"
  42.  
  43. #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
  44. #include <sys/param.h>
  45. #endif
  46.  
  47. #if !defined(macintosh)
  48. #include <sys/stat.h>
  49. #endif
  50.  
  51. #include <errno.h>
  52. #ifdef macintosh
  53. #include <unix.h>
  54. #else
  55. #include <fcntl.h>
  56. #endif
  57. #include <stdio.h>
  58. #include <stdlib.h>
  59. #include <string.h>
  60.  
  61. #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
  62. #include <unistd.h>
  63. #endif
  64.  
  65. #ifdef DEBUG
  66. #include <assert.h>
  67. #endif
  68.  
  69. #include "mcom_db.h"
  70. #include "hash.h"
  71. #include "page.h"
  72.  
  73. #ifndef NSPR20
  74. #if defined(__sun)
  75. # include "sunos4.h"
  76. #endif /* __sun */
  77. #endif /* NSPR20 */
  78.  
  79. /*
  80. #include "extern.h"
  81. */
  82. static int   alloc_segs __P((HTAB *, int));
  83. static int   flush_meta __P((HTAB *));
  84. static int   hash_access __P((HTAB *, ACTION, DBT *, DBT *));
  85. static int   hash_close __P((DB *));
  86. static int   hash_delete __P((const DB *, const DBT *, uint));
  87. static int   hash_fd __P((const DB *));
  88. static int   hash_get __P((const DB *, const DBT *, DBT *, uint));
  89. static int   hash_put __P((const DB *, DBT *, const DBT *, uint));
  90. static void *hash_realloc __P((SEGMENT **, int, int));
  91. static int   hash_seq __P((const DB *, DBT *, DBT *, uint));
  92. static int   hash_sync __P((const DB *, uint));
  93. static int   hdestroy __P((HTAB *));
  94. static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *));
  95. static int   init_htab __P((HTAB *, int));
  96. #if BYTE_ORDER == LITTLE_ENDIAN
  97. static void  swap_header __P((HTAB *));
  98. static void  swap_header_copy __P((HASHHDR *, HASHHDR *));
  99. #endif
  100.  
  101. /* Fast arithmetic, relying on powers of 2, */
  102. #define MOD(x, y)        ((x) & ((y) - 1))
  103.  
  104. #define RETURN_ERROR(ERR, LOC)    { save_errno = ERR; goto LOC; }
  105.  
  106. /* Return values */
  107. #define    SUCCESS     (0)
  108. #define    DBM_ERROR    (-1)
  109. #define    ABNORMAL (1)
  110.  
  111. #ifdef HASH_STATISTICS
  112. int hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  113. #endif
  114.  
  115. /* A new Lou (montulli@mozilla.com) routine.
  116.  *
  117.  * The database is screwed.  Delete it by 
  118.  * making it a zero length file
  119.  *
  120.  * This zero's hashp so that the
  121.  * database can't be accessed any more
  122.  */
  123. static void
  124. __remove_database(DB *dbp)
  125. {
  126.     HTAB *hashp = (HTAB *)dbp->internal;
  127.     if (!hashp)
  128.         return;
  129.  
  130.     if(hashp->fp != NO_FILE)
  131.         close(hashp->fp);
  132.     if(hashp->filename)
  133.         unlink(hashp->filename);
  134.     dbp->internal = NULL; /* zero the internal stuff */
  135.  
  136. }
  137.  
  138. /************************** INTERFACE ROUTINES ***************************/
  139. /* OPEN/CLOSE */
  140.  
  141.  
  142. extern DB *
  143. __hash_open(const char *file, int flags, int mode, const HASHINFO *info, int dflags)
  144. {
  145.     HTAB *hashp=NULL;
  146.     struct stat statbuf;
  147.     DB *dbp;
  148.     int bpages, hdrsize, new_table, nsegs, save_errno;
  149.  
  150.     if ((flags & O_ACCMODE) == O_WRONLY) {
  151.         errno = EINVAL;
  152.         RETURN_ERROR(ENOMEM, error0);
  153.     }
  154.  
  155.     /* zero the statbuffer so that
  156.      * we can check it for a non-zero
  157.      * date to see if stat succeeded
  158.      */
  159.     memset(&statbuf, 0, sizeof(struct stat));
  160.  
  161.     if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))
  162.         RETURN_ERROR(ENOMEM, error0);
  163.     hashp->fp = NO_FILE;
  164.     if(file)
  165.         hashp->filename = strdup(file);
  166.  
  167.     /*
  168.      * Even if user wants write only, we need to be able to read
  169.      * the actual file, so we need to open it read/write. But, the
  170.      * field in the hashp structure needs to be accurate so that
  171.      * we can check accesses.
  172.      */
  173.     hashp->flags = flags;
  174.  
  175.     new_table = 0;
  176.     if (!file || (flags & O_TRUNC)     || (stat(file, &statbuf)  && (errno == ENOENT))) 
  177.     {
  178.         if (errno == ENOENT)
  179.             errno = 0; /* Just in case someone looks at errno */
  180.         new_table = 1;
  181.     }
  182.     else if(statbuf.st_mtime && statbuf.st_size == 0)
  183.     {
  184.         /* check for a zero length file and delete it
  185.           * if it exists
  186.           */
  187.         new_table = 1;
  188.     }
  189.  
  190.     if (file) {                 
  191.  
  192. #if defined(_WIN32) || defined(_WINDOWS) || defined (macintosh)
  193.         if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1)
  194.             RETURN_ERROR(errno, error0);
  195. #else
  196.      if ((hashp->fp = open(file, flags, mode)) == -1)
  197.         RETURN_ERROR(errno, error0);
  198.     (void)fcntl(hashp->fp, F_SETFD, 1);
  199. /* We can't use fcntl because of NFS bugs. SIGH */
  200. #if 0
  201.     {
  202.     struct flock fl;
  203.     memset(&fl, 0, sizeof(fl));
  204.     fl.l_type = F_WRLCK;
  205.     if (fcntl(hashp->fp, F_SETLK, &fl) < 0) {
  206. #ifdef DEBUG
  207.         fprintf(stderr, "unable to open %s because it's locked (flags=0x%x)\n", file, flags);
  208. #endif
  209.         RETURN_ERROR(EACCES, error1);
  210.     }
  211.     }
  212. #endif
  213.  
  214. #endif
  215.     }
  216.     if (new_table) {
  217.         if (!init_hash(hashp, file, (HASHINFO *)info))
  218.             RETURN_ERROR(errno, error1);
  219.     } else {
  220.         /* Table already exists */
  221.         if (info && info->hash)
  222.             hashp->hash = info->hash;
  223.         else
  224.             hashp->hash = __default_hash;
  225.  
  226.         hdrsize = read(hashp->fp, (char *)&hashp->hdr, sizeof(HASHHDR));
  227. #if BYTE_ORDER == LITTLE_ENDIAN
  228.         swap_header(hashp);
  229. #endif
  230.         if (hdrsize == -1)
  231.             RETURN_ERROR(errno, error1);
  232.         if (hdrsize != sizeof(HASHHDR))
  233.             RETURN_ERROR(EFTYPE, error1);
  234.         /* Verify file type, versions and hash function */
  235.         if (hashp->MAGIC != HASHMAGIC)
  236.             RETURN_ERROR(EFTYPE, error1);
  237. #define    OLDHASHVERSION    1
  238.         if (hashp->VERSION != HASHVERSION &&
  239.             hashp->VERSION != OLDHASHVERSION)
  240.             RETURN_ERROR(EFTYPE, error1);
  241.         if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)
  242.             RETURN_ERROR(EFTYPE, error1);
  243.         if (hashp->NKEYS < 0) {
  244.             /*
  245.             ** OOPS. Old bad database from previously busted
  246.             ** code. Blow it away.
  247.             */
  248.             close(hashp->fp);
  249.             if (remove(file) < 0) {
  250. #if defined(DEBUG) && defined(XP_UNIX)
  251.             fprintf(stderr,
  252.                 "WARNING: You have an old bad cache.db file"
  253.                 " '%s', and I couldn't remove it!\n", file);
  254. #endif
  255.             } else {
  256. #if defined(DEBUG) && defined(XP_UNIX)
  257.             fprintf(stderr,
  258.                 "WARNING: I blew away your %s file because"
  259.                 " it was bad due to a recently fixed bug\n",
  260.                 file);
  261. #endif
  262.             }
  263.             RETURN_ERROR(ENOENT, error0);
  264.         }
  265.  
  266.         /*
  267.          * Figure out how many segments we need.  Max_Bucket is the
  268.          * maximum bucket number, so the number of buckets is
  269.          * max_bucket + 1.
  270.          */
  271.         nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) /
  272.              hashp->SGSIZE;
  273.         hashp->nsegs = 0;
  274.         if (alloc_segs(hashp, nsegs))
  275.             /*
  276.              * If alloc_segs fails, table will have been destroyed
  277.              * and errno will have been set.
  278.              */
  279.             RETURN_ERROR(ENOMEM, error0);
  280.         /* Read in bitmaps */
  281.         bpages = (hashp->SPARES[hashp->OVFL_POINT] +
  282.             (hashp->BSIZE << BYTE_SHIFT) - 1) >>
  283.             (hashp->BSHIFT + BYTE_SHIFT);
  284.  
  285.         hashp->nmaps = bpages;
  286.         (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32 *));
  287.     }
  288.  
  289.     /* Initialize Buffer Manager */
  290.     if (info && info->cachesize)
  291.         __buf_init(hashp, (int32) info->cachesize);
  292.     else
  293.         __buf_init(hashp, DEF_BUFSIZE);
  294.  
  295.     hashp->new_file = new_table;
  296. #ifdef macintosh
  297.     hashp->save_file = file && !(hashp->flags & O_RDONLY);
  298. #else
  299.     hashp->save_file = file && (hashp->flags & O_RDWR);
  300. #endif
  301.     hashp->cbucket = -1;
  302.     if (!(dbp = (DB *)malloc(sizeof(DB)))) {
  303.         save_errno = errno;
  304.         hdestroy(hashp);
  305.         errno = save_errno;
  306.         RETURN_ERROR(ENOMEM, error0);
  307.     }
  308.     dbp->internal = hashp;
  309.     dbp->close = hash_close;
  310.     dbp->del = hash_delete;
  311.     dbp->fd = hash_fd;
  312.     dbp->get = hash_get;
  313.     dbp->put = hash_put;
  314.     dbp->seq = hash_seq;
  315.     dbp->sync = hash_sync;
  316.     dbp->type = DB_HASH;
  317.  
  318. #if 0
  319. #if defined(DEBUG) && !defined(_WINDOWS)
  320. {
  321. extern int MKLib_trace_flag;
  322.  
  323.   if(MKLib_trace_flag)
  324.     (void)fprintf(stderr,
  325. "%s\n%s%lx\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
  326.         "init_htab:",
  327.         "TABLE POINTER   ", (unsigned long) hashp,
  328.         "BUCKET SIZE     ", hashp->BSIZE,
  329.         "BUCKET SHIFT    ", hashp->BSHIFT,
  330.         "DIRECTORY SIZE  ", hashp->DSIZE,
  331.         "SEGMENT SIZE    ", hashp->SGSIZE,
  332.         "SEGMENT SHIFT   ", hashp->SSHIFT,
  333.         "FILL FACTOR     ", hashp->FFACTOR,
  334.         "MAX BUCKET      ", hashp->MAX_BUCKET,
  335.         "OVFL POINT         ", hashp->OVFL_POINT,
  336.         "LAST FREED      ", hashp->LAST_FREED,
  337.         "HIGH MASK       ", hashp->HIGH_MASK,
  338.         "LOW  MASK       ", hashp->LOW_MASK,
  339.         "NSEGS           ", hashp->nsegs,
  340.         "NKEYS           ", hashp->NKEYS);
  341. }
  342. #endif
  343. #endif /* 0 */
  344. #ifdef HASH_STATISTICS
  345.     hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
  346. #endif
  347.     return (dbp);
  348.  
  349. error1:
  350.     if (hashp != NULL)
  351.         (void)close(hashp->fp);
  352.  
  353. error0:
  354.     free(hashp);
  355.     errno = save_errno;
  356.     return (NULL);
  357. }
  358.  
  359. static int
  360. hash_close(DB *dbp)
  361. {
  362.     HTAB *hashp;
  363.     int retval;
  364.  
  365.     if (!dbp)
  366.         return (DBM_ERROR);
  367.  
  368.     hashp = (HTAB *)dbp->internal;
  369.     if(!hashp)
  370.         return (DBM_ERROR);
  371.  
  372.     retval = hdestroy(hashp);
  373.     free(dbp);
  374.     return (retval);
  375. }
  376.  
  377. static int hash_fd(const DB *dbp)
  378. {
  379.     HTAB *hashp;
  380.  
  381.     if (!dbp)
  382.         return (DBM_ERROR);
  383.  
  384.     hashp = (HTAB *)dbp->internal;
  385.     if(!hashp)
  386.         return (DBM_ERROR);
  387.  
  388.     if (hashp->fp == -1) {
  389.         errno = ENOENT;
  390.         return (-1);
  391.     }
  392.     return (hashp->fp);
  393. }
  394.  
  395. /************************** LOCAL CREATION ROUTINES **********************/
  396. static HTAB *
  397. init_hash(HTAB *hashp, const char *file, HASHINFO *info)
  398. {
  399.     struct stat statbuf;
  400.     int nelem;
  401.  
  402.     nelem = 1;
  403.     hashp->NKEYS = 0;
  404.     hashp->LORDER = BYTE_ORDER;
  405.     hashp->BSIZE = DEF_BUCKET_SIZE;
  406.     hashp->BSHIFT = DEF_BUCKET_SHIFT;
  407.     hashp->SGSIZE = DEF_SEGSIZE;
  408.     hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
  409.     hashp->DSIZE = DEF_DIRSIZE;
  410.     hashp->FFACTOR = DEF_FFACTOR;
  411.     hashp->hash = __default_hash;
  412.     memset(hashp->SPARES, 0, sizeof(hashp->SPARES));
  413.     memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));
  414.  
  415.     /* Fix bucket size to be optimal for file system */
  416.     if (file != NULL) {
  417.         if (stat(file, &statbuf))
  418.             return (NULL);
  419.  
  420. #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh)
  421.         hashp->BSIZE = statbuf.st_blksize;
  422.  
  423.            /* new code added by Lou to reduce block
  424.             * size down below MAX_BSIZE
  425.             */
  426.            if (hashp->BSIZE > MAX_BSIZE)
  427.                hashp->BSIZE = MAX_BSIZE;
  428. #endif
  429.         hashp->BSHIFT = __log2(hashp->BSIZE);
  430.     }
  431.  
  432.     if (info) {
  433.         if (info->bsize) {
  434.             /* Round pagesize up to power of 2 */
  435.             hashp->BSHIFT = __log2(info->bsize);
  436.             hashp->BSIZE = 1 << hashp->BSHIFT;
  437.             if (hashp->BSIZE > MAX_BSIZE) {
  438.                 errno = EINVAL;
  439.                 return (NULL);
  440.             }
  441.         }
  442.         if (info->ffactor)
  443.             hashp->FFACTOR = info->ffactor;
  444.         if (info->hash)
  445.             hashp->hash = info->hash;
  446.         if (info->nelem)
  447.             nelem = info->nelem;
  448.         if (info->lorder) {
  449.             if (info->lorder != BIG_ENDIAN &&
  450.                 info->lorder != LITTLE_ENDIAN) {
  451.                 errno = EINVAL;
  452.                 return (NULL);
  453.             }
  454.             hashp->LORDER = info->lorder;
  455.         }
  456.     }
  457.     /* init_htab should destroy the table and set errno if it fails */
  458.     if (init_htab(hashp, nelem))
  459.         return (NULL);
  460.     else
  461.         return (hashp);
  462. }
  463. /*
  464.  * This calls alloc_segs which may run out of memory.  Alloc_segs will destroy
  465.  * the table and set errno, so we just pass the error information along.
  466.  *
  467.  * Returns 0 on No Error
  468.  */
  469. static int
  470. init_htab(HTAB *hashp, int nelem)
  471. {
  472.     register int nbuckets, nsegs;
  473.     int l2;
  474.  
  475.     /*
  476.      * Divide number of elements by the fill factor and determine a
  477.      * desired number of buckets.  Allocate space for the next greater
  478.      * power of two number of buckets.
  479.      */
  480.     nelem = (nelem - 1) / hashp->FFACTOR + 1;
  481.  
  482.     l2 = __log2(MAX(nelem, 2));
  483.     nbuckets = 1 << l2;
  484.  
  485.     hashp->SPARES[l2] = l2 + 1;
  486.     hashp->SPARES[l2 + 1] = l2 + 1;
  487.     hashp->OVFL_POINT = l2;
  488.     hashp->LAST_FREED = 2;
  489.  
  490.     /* First bitmap page is at: splitpoint l2 page offset 1 */
  491.     if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))
  492.         return (-1);
  493.  
  494.     hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
  495.     hashp->HIGH_MASK = (nbuckets << 1) - 1;
  496.     hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>
  497.         hashp->BSHIFT) + 1;
  498.  
  499.     nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
  500.     nsegs = 1 << __log2(nsegs);
  501.  
  502.     if (nsegs > hashp->DSIZE)
  503.         hashp->DSIZE = nsegs;
  504.     return (alloc_segs(hashp, nsegs));
  505. }
  506.  
  507. /********************** DESTROY/CLOSE ROUTINES ************************/
  508.  
  509. /*
  510.  * Flushes any changes to the file if necessary and destroys the hashp
  511.  * structure, freeing all allocated space.
  512.  */
  513. static int
  514. hdestroy(HTAB *hashp)
  515. {
  516.     int i, save_errno;
  517.  
  518.     save_errno = 0;
  519.  
  520. #ifdef HASH_STATISTICS
  521.     (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
  522.         hash_accesses, hash_collisions);
  523.     (void)fprintf(stderr, "hdestroy: expansions %ld\n",
  524.         hash_expansions);
  525.     (void)fprintf(stderr, "hdestroy: overflows %ld\n",
  526.         hash_overflows);
  527.     (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
  528.         hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
  529.  
  530.     for (i = 0; i < NCACHED; i++)
  531.         (void)fprintf(stderr,
  532.             "spares[%d] = %d\n", i, hashp->SPARES[i]);
  533. #endif
  534.     /*
  535.      * Call on buffer manager to free buffers, and if required,
  536.      * write them to disk.
  537.      */
  538.     if (__buf_free(hashp, 1, hashp->save_file))
  539.         save_errno = errno;
  540.     if (hashp->dir) {
  541.         free(*hashp->dir);    /* Free initial segments */
  542.         /* Free extra segments */
  543.         while (hashp->exsegs--)
  544.             free(hashp->dir[--hashp->nsegs]);
  545.         free(hashp->dir);
  546.     }
  547.     if (flush_meta(hashp) && !save_errno)
  548.         save_errno = errno;
  549.     /* Free Bigmaps */
  550.     for (i = 0; i < hashp->nmaps; i++)
  551.         if (hashp->mapp[i])
  552.             free(hashp->mapp[i]);
  553.  
  554.     if (hashp->fp != -1)
  555.         (void)close(hashp->fp);
  556.  
  557.     if(hashp->filename)
  558.         free(hashp->filename);
  559.  
  560.     free(hashp);
  561.  
  562.     if (save_errno) {
  563.         errno = save_errno;
  564.         return (DBM_ERROR);
  565.     }
  566.     return (SUCCESS);
  567. }
  568. /*
  569.  * Write modified pages to disk
  570.  *
  571.  * Returns:
  572.  *     0 == OK
  573.  *    -1 DBM_ERROR
  574.  */
  575. static int
  576. hash_sync(const DB *dbp, uint flags)
  577. {
  578.     HTAB *hashp;
  579.  
  580.     if (flags != 0) {
  581.         errno = EINVAL;
  582.         return (DBM_ERROR);
  583.     }
  584.  
  585.     if (!dbp)
  586.         return (DBM_ERROR);
  587.  
  588.     hashp = (HTAB *)dbp->internal;
  589.     if(!hashp)
  590.         return (DBM_ERROR);
  591.  
  592.     if (!hashp->save_file)
  593.         return (0);
  594.     if (__buf_free(hashp, 0, 1) || flush_meta(hashp))
  595.         return (DBM_ERROR);
  596.     hashp->new_file = 0;
  597.     return (0);
  598. }
  599.  
  600. /*
  601.  * Returns:
  602.  *     0 == OK
  603.  *    -1 indicates that errno should be set
  604.  */
  605. static int
  606. flush_meta(HTAB *hashp)
  607. {
  608.     HASHHDR *whdrp;
  609. #if BYTE_ORDER == LITTLE_ENDIAN
  610.     HASHHDR whdr;
  611. #endif
  612.     int fp, i, wsize;
  613.  
  614.     if (!hashp->save_file)
  615.         return (0);
  616.     hashp->MAGIC = HASHMAGIC;
  617.     hashp->VERSION = HASHVERSION;
  618.     hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
  619.  
  620.     fp = hashp->fp;
  621.     whdrp = &hashp->hdr;
  622. #if BYTE_ORDER == LITTLE_ENDIAN
  623.     whdrp = &whdr;
  624.     swap_header_copy(&hashp->hdr, whdrp);
  625. #endif
  626.     if ((lseek(fp, (off_t)0, SEEK_SET) == -1) ||
  627.         ((wsize = write(fp, (char*)whdrp, sizeof(HASHHDR))) == -1))
  628.         return (-1);
  629.     else
  630.         if (wsize != sizeof(HASHHDR)) {
  631.             errno = EFTYPE;
  632.             hashp->dbmerrno = errno;
  633.             return (-1);
  634.         }
  635.     for (i = 0; i < NCACHED; i++)
  636.         if (hashp->mapp[i])
  637.             if (__put_page(hashp, (char *)hashp->mapp[i],
  638.                 hashp->BITMAPS[i], 0, 1))
  639.                 return (-1);
  640.     return (0);
  641. }
  642.  
  643. /*******************************SEARCH ROUTINES *****************************/
  644. /*
  645.  * All the access routines return
  646.  *
  647.  * Returns:
  648.  *     0 on SUCCESS
  649.  *     1 to indicate an external DBM_ERROR (i.e. key not found, etc)
  650.  *    -1 to indicate an internal DBM_ERROR (i.e. out of memory, etc)
  651.  */
  652. static int
  653. hash_get(
  654.     const DB *dbp,
  655.     const DBT *key,
  656.     DBT *data,
  657.     uint flag)
  658. {
  659.     HTAB *hashp;
  660.     int rv;
  661.  
  662.     hashp = (HTAB *)dbp->internal;
  663.     if (!hashp)
  664.         return (DBM_ERROR);
  665.  
  666.     if (flag) {
  667.         hashp->dbmerrno = errno = EINVAL;
  668.         return (DBM_ERROR);
  669.     }
  670.  
  671.     rv = hash_access(hashp, HASH_GET, (DBT *)key, data);
  672.  
  673.     if(rv == DATABASE_CORRUPTED_ERROR)
  674.       {
  675. #if defined(unix) && defined(DEBUG)
  676.         printf("\n\nDBM Database has been corrupted, tell Lou...\n\n");
  677. #endif
  678.           __remove_database((DB *)dbp);
  679.       }
  680.  
  681.     return(rv);
  682. }
  683.  
  684. static int
  685. hash_put(
  686.     const DB *dbp,
  687.     DBT *key,
  688.     const DBT *data,
  689.     uint flag)
  690. {
  691.     HTAB *hashp;
  692.     int rv;
  693.  
  694.     hashp = (HTAB *)dbp->internal;
  695.     if (!hashp)
  696.         return (DBM_ERROR);
  697.  
  698.     if (flag && flag != R_NOOVERWRITE) {
  699.         hashp->dbmerrno = errno = EINVAL;
  700.         return (DBM_ERROR);
  701.     }
  702.     if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
  703.         hashp->dbmerrno = errno = EPERM;
  704.         return (DBM_ERROR);
  705.     }
  706.  
  707.     rv =  hash_access(hashp, flag == R_NOOVERWRITE ?
  708.         HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data);
  709.  
  710.     if(rv == DATABASE_CORRUPTED_ERROR)
  711.       {
  712. #if defined(unix) && defined(DEBUG)
  713.         printf("\n\nDBM Database has been corrupted, tell Lou...\n\n");
  714. #endif
  715.           __remove_database((DB *)dbp);
  716.       }
  717.  
  718.     return(rv);
  719. }
  720.  
  721. static int
  722. hash_delete(
  723.     const DB *dbp,
  724.     const DBT *key,
  725.     uint flag)        /* Ignored */
  726. {
  727.     HTAB *hashp;
  728.     int rv;
  729.  
  730.     hashp = (HTAB *)dbp->internal;
  731.     if (!hashp)
  732.         return (DBM_ERROR);
  733.  
  734.     if (flag && flag != R_CURSOR) {
  735.         hashp->dbmerrno = errno = EINVAL;
  736.         return (DBM_ERROR);
  737.     }
  738.     if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
  739.         hashp->dbmerrno = errno = EPERM;
  740.         return (DBM_ERROR);
  741.     }
  742.     rv = hash_access(hashp, HASH_DELETE, (DBT *)key, NULL);
  743.  
  744.     if(rv == DATABASE_CORRUPTED_ERROR)
  745.       {
  746. #if defined(unix) && defined(DEBUG)
  747.         printf("\n\nDBM Database has been corrupted, tell Lou...\n\n");
  748. #endif
  749.           __remove_database((DB *)dbp);
  750.       }
  751.  
  752.     return(rv);
  753. }
  754.  
  755. #define MAX_OVERFLOW_HASH_ACCESS_LOOPS 2000
  756. /*
  757.  * Assume that hashp has been set in wrapper routine.
  758.  */
  759. static int
  760. hash_access(
  761.     HTAB *hashp,
  762.     ACTION action,
  763.     DBT *key, DBT *val)
  764. {
  765.     register BUFHEAD *rbufp;
  766.     BUFHEAD *bufp, *save_bufp;
  767.     register uint16 *bp;
  768.     register long n, ndx, off, size;
  769.     register char *kp;
  770.     uint16 pageno;
  771.     uint32 ovfl_loop_count=0;
  772.     int32 last_overflow_page_no = -1;
  773.  
  774. #ifdef HASH_STATISTICS
  775.     hash_accesses++;
  776. #endif
  777.  
  778.     off = hashp->BSIZE;
  779.     size = key->size;
  780.     kp = (char *)key->data;
  781.     rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);
  782.     if (!rbufp)
  783.         return (DATABASE_CORRUPTED_ERROR);
  784.     save_bufp = rbufp;
  785.  
  786.     /* Pin the bucket chain */
  787.     rbufp->flags |= BUF_PIN;
  788.     for (bp = (uint16 *)rbufp->page, n = *bp++, ndx = 1; ndx < n;)
  789.     {
  790.  
  791.         if (bp[1] >= REAL_KEY) {
  792.             /* Real key/data pair */
  793.             if (size == off - *bp &&
  794.                 memcmp(kp, rbufp->page + *bp, size) == 0)
  795.                 goto found;
  796.             off = bp[1];
  797. #ifdef HASH_STATISTICS
  798.             hash_collisions++;
  799. #endif
  800.             bp += 2;
  801.             ndx += 2;
  802.         } else if (bp[1] == OVFLPAGE) {
  803.  
  804.             /* database corruption: overflow loop detection */
  805.             if(last_overflow_page_no == (int32)*bp)
  806.                 return (DATABASE_CORRUPTED_ERROR);
  807.  
  808.             last_overflow_page_no = *bp;
  809.  
  810.             rbufp = __get_buf(hashp, *bp, rbufp, 0);
  811.             if (!rbufp) {
  812.                 save_bufp->flags &= ~BUF_PIN;
  813.                 return (DBM_ERROR);
  814.             }
  815.  
  816.             ovfl_loop_count++;
  817.             if(ovfl_loop_count > MAX_OVERFLOW_HASH_ACCESS_LOOPS)
  818.                 return (DATABASE_CORRUPTED_ERROR);
  819.  
  820.             /* FOR LOOP INIT */
  821.             bp = (uint16 *)rbufp->page;
  822.             n = *bp++;
  823.             ndx = 1;
  824.             off = hashp->BSIZE;
  825.                         } else if (bp[1] < REAL_KEY) {
  826.             if ((ndx =
  827.                 __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0)
  828.                 goto found;
  829.             if (ndx == -2) {
  830.                 bufp = rbufp;
  831.                 if (!(pageno =
  832.                     __find_last_page(hashp, &bufp))) {
  833.                     ndx = 0;
  834.                     rbufp = bufp;
  835.                     break;    /* FOR */
  836.                 }
  837.                 rbufp = __get_buf(hashp, pageno, bufp, 0);
  838.                 if (!rbufp) {
  839.                     save_bufp->flags &= ~BUF_PIN;
  840.                     return (DBM_ERROR);
  841.                 }
  842.                 /* FOR LOOP INIT */
  843.                 bp = (uint16 *)rbufp->page;
  844.                 n = *bp++;
  845.                 ndx = 1;
  846.                 off = hashp->BSIZE;
  847.             } else {
  848.                 save_bufp->flags &= ~BUF_PIN;
  849.                 return (DBM_ERROR);
  850.  
  851.             }
  852.         }
  853.     }
  854.  
  855.     /* Not found */
  856.     switch (action) {
  857.     case HASH_PUT:
  858.     case HASH_PUTNEW:
  859.         if (__addel(hashp, rbufp, key, val)) {
  860.             save_bufp->flags &= ~BUF_PIN;
  861.             return (DBM_ERROR);
  862.         } else {
  863.             save_bufp->flags &= ~BUF_PIN;
  864.             return (SUCCESS);
  865.         }
  866.     case HASH_GET:
  867.     case HASH_DELETE:
  868.     default:
  869.         save_bufp->flags &= ~BUF_PIN;
  870.         return (ABNORMAL);
  871.     }
  872.  
  873. found:
  874.     switch (action) {
  875.     case HASH_PUTNEW:
  876.         save_bufp->flags &= ~BUF_PIN;
  877.         return (ABNORMAL);
  878.     case HASH_GET:
  879.         bp = (uint16 *)rbufp->page;
  880.         if (bp[ndx + 1] < REAL_KEY) {
  881.             if (__big_return(hashp, rbufp, ndx, val, 0))
  882.                 return (DBM_ERROR);
  883.         } else {
  884.             val->data = (uint8 *)rbufp->page + (int)bp[ndx + 1];
  885.             val->size = bp[ndx] - bp[ndx + 1];
  886.         }
  887.         break;
  888.     case HASH_PUT:
  889.         if ((__delpair(hashp, rbufp, ndx)) ||
  890.             (__addel(hashp, rbufp, key, val))) {
  891.             save_bufp->flags &= ~BUF_PIN;
  892.             return (DBM_ERROR);
  893.         }
  894.         break;
  895.     case HASH_DELETE:
  896.         if (__delpair(hashp, rbufp, ndx))
  897.             return (DBM_ERROR);
  898.         break;
  899.     default:
  900.         abort();
  901.     }
  902.     save_bufp->flags &= ~BUF_PIN;
  903.     return (SUCCESS);
  904. }
  905.  
  906. static int
  907. hash_seq(
  908.     const DB *dbp,
  909.     DBT *key, DBT *data,
  910.     uint flag)
  911. {
  912.     register uint32 bucket;
  913.     register BUFHEAD *bufp;
  914.     HTAB *hashp;
  915.     uint16 *bp, ndx;
  916.  
  917.     hashp = (HTAB *)dbp->internal;
  918.     if (!hashp)
  919.         return (DBM_ERROR);
  920.  
  921.     if (flag && flag != R_FIRST && flag != R_NEXT) {
  922.         hashp->dbmerrno = errno = EINVAL;
  923.         return (DBM_ERROR);
  924.     }
  925. #ifdef HASH_STATISTICS
  926.     hash_accesses++;
  927. #endif
  928.     if ((hashp->cbucket < 0) || (flag == R_FIRST)) {
  929.         hashp->cbucket = 0;
  930.         hashp->cndx = 1;
  931.         hashp->cpage = NULL;
  932.     }
  933.  
  934.     for (bp = NULL; !bp || !bp[0]; ) {
  935.         if (!(bufp = hashp->cpage)) {
  936.             for (bucket = hashp->cbucket;
  937.                 bucket <= hashp->MAX_BUCKET;
  938.                 bucket++, hashp->cndx = 1) {
  939.                 bufp = __get_buf(hashp, bucket, NULL, 0);
  940.                 if (!bufp)
  941.                     return (DBM_ERROR);
  942.                 hashp->cpage = bufp;
  943.                 bp = (uint16 *)bufp->page;
  944.                 if (bp[0])
  945.                     break;
  946.             }
  947.             hashp->cbucket = bucket;
  948.             if (hashp->cbucket > hashp->MAX_BUCKET) {
  949.                 hashp->cbucket = -1;
  950.                 return (ABNORMAL);
  951.             }
  952.         } else
  953.             bp = (uint16 *)hashp->cpage->page;
  954.  
  955. #ifdef DEBUG
  956.         assert(bp);
  957.         assert(bufp);
  958. #endif
  959.         while (bp[hashp->cndx + 1] == OVFLPAGE) {
  960.             bufp = hashp->cpage =
  961.                 __get_buf(hashp, bp[hashp->cndx], bufp, 0);
  962.             if (!bufp)
  963.                 return (DBM_ERROR);
  964.             bp = (uint16 *)(bufp->page);
  965.             hashp->cndx = 1;
  966.         }
  967.         if (!bp[0]) {
  968.             hashp->cpage = NULL;
  969.             ++hashp->cbucket;
  970.         }
  971.     }
  972.     ndx = hashp->cndx;
  973.     if (bp[ndx + 1] < REAL_KEY) {
  974.         if (__big_keydata(hashp, bufp, key, data, 1))
  975.             return (DBM_ERROR);
  976.     } else {
  977.         key->data = (uint8 *)hashp->cpage->page + bp[ndx];
  978.         key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
  979.         data->data = (uint8 *)hashp->cpage->page + bp[ndx + 1];
  980.         data->size = bp[ndx] - bp[ndx + 1];
  981.         ndx += 2;
  982.         if (ndx > bp[0]) {
  983.             hashp->cpage = NULL;
  984.             hashp->cbucket++;
  985.             hashp->cndx = 1;
  986.         } else
  987.             hashp->cndx = ndx;
  988.     }
  989.     return (SUCCESS);
  990. }
  991.  
  992. /********************************* UTILITIES ************************/
  993.  
  994. /*
  995.  * Returns:
  996.  *     0 ==> OK
  997.  *    -1 ==> Error
  998.  */
  999. extern int
  1000. __expand_table(HTAB *hashp)
  1001. {
  1002.     uint32 old_bucket, new_bucket;
  1003.     int dirsize, new_segnum, spare_ndx;
  1004.  
  1005. #ifdef HASH_STATISTICS
  1006.     hash_expansions++;
  1007. #endif
  1008.     new_bucket = ++hashp->MAX_BUCKET;
  1009.     old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
  1010.  
  1011.     new_segnum = new_bucket >> hashp->SSHIFT;
  1012.  
  1013.     /* Check if we need a new segment */
  1014.     if (new_segnum >= hashp->nsegs) {
  1015.         /* Check if we need to expand directory */
  1016.         if (new_segnum >= hashp->DSIZE) {
  1017.             /* Reallocate directory */
  1018.             dirsize = hashp->DSIZE * sizeof(SEGMENT *);
  1019.             if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))
  1020.                 return (-1);
  1021.             hashp->DSIZE = dirsize << 1;
  1022.         }
  1023.         if ((hashp->dir[new_segnum] =
  1024.             (SEGMENT)calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL)
  1025.             return (-1);
  1026.         hashp->exsegs++;
  1027.         hashp->nsegs++;
  1028.     }
  1029.     /*
  1030.      * If the split point is increasing (MAX_BUCKET's log base 2
  1031.      * * increases), we need to copy the current contents of the spare
  1032.      * split bucket to the next bucket.
  1033.      */
  1034.     spare_ndx = __log2(hashp->MAX_BUCKET + 1);
  1035.     if (spare_ndx > hashp->OVFL_POINT) {
  1036.         hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
  1037.         hashp->OVFL_POINT = spare_ndx;
  1038.     }
  1039.  
  1040.     if (new_bucket > hashp->HIGH_MASK) {
  1041.         /* Starting a new doubling */
  1042.         hashp->LOW_MASK = hashp->HIGH_MASK;
  1043.         hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
  1044.     }
  1045.     /* Relocate records to the new bucket */
  1046.     return (__split_page(hashp, old_bucket, new_bucket));
  1047. }
  1048.  
  1049. /*
  1050.  * If realloc guarantees that the pointer is not destroyed if the realloc
  1051.  * fails, then this routine can go away.
  1052.  */
  1053. static void *
  1054. hash_realloc(
  1055.     SEGMENT **p_ptr,
  1056.     int oldsize, int newsize)
  1057. {
  1058.     register void *p;
  1059.  
  1060.     if ((p = malloc(newsize))) {
  1061.         memmove(p, *p_ptr, oldsize);
  1062.         memset((char *)p + oldsize, 0, newsize - oldsize);
  1063.         free(*p_ptr);
  1064.         *p_ptr = (SEGMENT *)p;
  1065.     }
  1066.     return (p);
  1067. }
  1068.  
  1069. extern uint32
  1070. __call_hash(HTAB *hashp, char *k, int len)
  1071. {
  1072.     uint32 n, bucket;
  1073.  
  1074.     n = hashp->hash(k, len);
  1075.     bucket = n & hashp->HIGH_MASK;
  1076.     if (bucket > hashp->MAX_BUCKET)
  1077.         bucket = bucket & hashp->LOW_MASK;
  1078.     return (bucket);
  1079. }
  1080.  
  1081. /*
  1082.  * Allocate segment table.  On error, destroy the table and set errno.
  1083.  *
  1084.  * Returns 0 on success
  1085.  */
  1086. static int
  1087. alloc_segs(
  1088.     HTAB *hashp,
  1089.     int nsegs)
  1090. {
  1091.     register int i;
  1092.     register SEGMENT store;
  1093.  
  1094.     int save_errno;
  1095.  
  1096.     if ((hashp->dir =
  1097.         (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) {
  1098.         save_errno = errno;
  1099.         (void)hdestroy(hashp);
  1100.         errno = save_errno;
  1101.         return (-1);
  1102.     }
  1103.     /* Allocate segments */
  1104.     if ((store =
  1105.         (SEGMENT)calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {
  1106.         save_errno = errno;
  1107.         (void)hdestroy(hashp);
  1108.         errno = save_errno;
  1109.         return (-1);
  1110.     }
  1111.     for (i = 0; i < nsegs; i++, hashp->nsegs++)
  1112.         hashp->dir[i] = &store[i << hashp->SSHIFT];
  1113.     return (0);
  1114. }
  1115.  
  1116. #if BYTE_ORDER == LITTLE_ENDIAN
  1117. /*
  1118.  * Hashp->hdr needs to be byteswapped.
  1119.  */
  1120. static void
  1121. swap_header_copy(
  1122.     HASHHDR *srcp, HASHHDR *destp)
  1123. {
  1124.     int i;
  1125.  
  1126.     P_32_COPY(srcp->magic, destp->magic);
  1127.     P_32_COPY(srcp->version, destp->version);
  1128.     P_32_COPY(srcp->lorder, destp->lorder);
  1129.     P_32_COPY(srcp->bsize, destp->bsize);
  1130.     P_32_COPY(srcp->bshift, destp->bshift);
  1131.     P_32_COPY(srcp->dsize, destp->dsize);
  1132.     P_32_COPY(srcp->ssize, destp->ssize);
  1133.     P_32_COPY(srcp->sshift, destp->sshift);
  1134.     P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
  1135.     P_32_COPY(srcp->last_freed, destp->last_freed);
  1136.     P_32_COPY(srcp->max_bucket, destp->max_bucket);
  1137.     P_32_COPY(srcp->high_mask, destp->high_mask);
  1138.     P_32_COPY(srcp->low_mask, destp->low_mask);
  1139.     P_32_COPY(srcp->ffactor, destp->ffactor);
  1140.     P_32_COPY(srcp->nkeys, destp->nkeys);
  1141.     P_32_COPY(srcp->hdrpages, destp->hdrpages);
  1142.     P_32_COPY(srcp->h_charkey, destp->h_charkey);
  1143.     for (i = 0; i < NCACHED; i++) {
  1144.         P_32_COPY(srcp->spares[i], destp->spares[i]);
  1145.         P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
  1146.     }
  1147. }
  1148.  
  1149. static void
  1150. swap_header(HTAB *hashp)
  1151. {
  1152.     HASHHDR *hdrp;
  1153.     int i;
  1154.  
  1155.     hdrp = &hashp->hdr;
  1156.  
  1157.     M_32_SWAP(hdrp->magic);
  1158.     M_32_SWAP(hdrp->version);
  1159.     M_32_SWAP(hdrp->lorder);
  1160.     M_32_SWAP(hdrp->bsize);
  1161.     M_32_SWAP(hdrp->bshift);
  1162.     M_32_SWAP(hdrp->dsize);
  1163.     M_32_SWAP(hdrp->ssize);
  1164.     M_32_SWAP(hdrp->sshift);
  1165.     M_32_SWAP(hdrp->ovfl_point);
  1166.     M_32_SWAP(hdrp->last_freed);
  1167.     M_32_SWAP(hdrp->max_bucket);
  1168.     M_32_SWAP(hdrp->high_mask);
  1169.     M_32_SWAP(hdrp->low_mask);
  1170.     M_32_SWAP(hdrp->ffactor);
  1171.     M_32_SWAP(hdrp->nkeys);
  1172.     M_32_SWAP(hdrp->hdrpages);
  1173.     M_32_SWAP(hdrp->h_charkey);
  1174.     for (i = 0; i < NCACHED; i++) {
  1175.         M_32_SWAP(hdrp->spares[i]);
  1176.         M_16_SWAP(hdrp->bitmaps[i]);
  1177.     }
  1178. }
  1179. #endif
  1180.