Back to index

lightning-sunbird  0.9+nobinonly
hash.c
Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993, 1994
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Margo Seltzer.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. ***REMOVED*** - see 
00017  *    ftp://ftp.cs.berkeley.edu/pub/4bsd/README.Impt.License.Change
00018  * 4. Neither the name of the University nor the names of its contributors
00019  *    may be used to endorse or promote products derived from this software
00020  *    without specific prior written permission.
00021  *
00022  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00023  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00024  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00025  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00026  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00027  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00028  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00029  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00030  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00031  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00032  * SUCH DAMAGE.
00033  */
00034 
00035 #if defined(LIBC_SCCS) && !defined(lint)
00036 static char sccsid[] = "@(#)hash.c 8.9 (Berkeley) 6/16/94";
00037 #endif /* LIBC_SCCS and not lint */
00038 
00039 #include "watcomfx.h"
00040 
00041 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && !defined(XP_OS2_VACPP)
00042 #include <sys/param.h>
00043 #endif
00044 
00045 #if !defined(macintosh)
00046 #ifdef XP_OS2_EMX
00047 #include <sys/types.h>
00048 #endif
00049 #include <sys/stat.h>
00050 #endif
00051 
00052 #if defined(macintosh)
00053 #include <unix.h>
00054 #include <unistd.h>
00055 #endif
00056 
00057 #include <errno.h>
00058 #include <fcntl.h>
00059 #include <stdio.h>
00060 #include <stdlib.h>
00061 #include <string.h>
00062 
00063 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && !defined(XP_OS2_VACPP)
00064 #include <unistd.h>
00065 #endif
00066 #if defined(_WIN32) || defined(_WINDOWS) 
00067 #include <windows.h>
00068 #endif
00069 
00070 #include <assert.h>
00071 
00072 #include "mcom_db.h"
00073 #include "hash.h"
00074 #include "page.h"
00075 
00076 /*
00077 #include "extern.h"
00078 */
00079 static int   alloc_segs __P((HTAB *, int));
00080 static int   flush_meta __P((HTAB *));
00081 static int   hash_access __P((HTAB *, ACTION, DBT *, DBT *));
00082 static int   hash_close __P((DB *));
00083 static int   hash_delete __P((const DB *, const DBT *, uint));
00084 static int   hash_fd __P((const DB *));
00085 static int   hash_get __P((const DB *, const DBT *, DBT *, uint));
00086 static int   hash_put __P((const DB *, DBT *, const DBT *, uint));
00087 static void *hash_realloc __P((SEGMENT **, size_t, size_t));
00088 static int   hash_seq __P((const DB *, DBT *, DBT *, uint));
00089 static int   hash_sync __P((const DB *, uint));
00090 static int   hdestroy __P((HTAB *));
00091 static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *));
00092 static int   init_htab __P((HTAB *, int));
00093 #if BYTE_ORDER == LITTLE_ENDIAN
00094 static void  swap_header __P((HTAB *));
00095 static void  swap_header_copy __P((HASHHDR *, HASHHDR *));
00096 #endif
00097 
00098 /* Fast arithmetic, relying on powers of 2, */
00099 #define MOD(x, y)           ((x) & ((y) - 1))
00100 
00101 #define RETURN_ERROR(ERR, LOC)     { save_errno = ERR; goto LOC; }
00102 
00103 /* Return values */
00104 #define       SUCCESS        (0)
00105 #define       DBM_ERROR     (-1)
00106 #define       ABNORMAL (1)
00107 
00108 #ifdef HASH_STATISTICS
00109 int hash_accesses, hash_collisions, hash_expansions, hash_overflows;
00110 #endif
00111 
00112 /* A new Lou (montulli@mozilla.com) routine.
00113  *
00114  * The database is screwed.  
00115  *
00116  * This closes the file, flushing buffers as appropriate.
00117  */
00118 static void
00119 __remove_database(DB *dbp)
00120 {
00121        HTAB *hashp = (HTAB *)dbp->internal;
00122 
00123        assert(0);
00124 
00125        if (!hashp)
00126               return;
00127        hdestroy(hashp);
00128        dbp->internal = NULL; 
00129 }
00130 
00131 /************************** INTERFACE ROUTINES ***************************/
00132 /* OPEN/CLOSE */
00133 
00134 
00135 extern DB *
00136 __hash_open(const char *file, int flags, int mode, const HASHINFO *info, int dflags)
00137 {
00138        HTAB *hashp=NULL;
00139        struct stat statbuf;
00140        DB *dbp;
00141        int bpages, hdrsize, new_table, nsegs, save_errno;
00142 
00143        if ((flags & O_ACCMODE) == O_WRONLY) {
00144               errno = EINVAL;
00145               return NULL;
00146        }
00147 
00148        /* zero the statbuffer so that
00149         * we can check it for a non-zero
00150         * date to see if stat succeeded
00151         */
00152        memset(&statbuf, 0, sizeof(struct stat));
00153 
00154        if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) {
00155               errno = ENOMEM;
00156               return NULL;
00157        }
00158        hashp->fp = NO_FILE;
00159        if(file)
00160               hashp->filename = strdup(file);
00161 
00162        /*
00163         * Even if user wants write only, we need to be able to read
00164         * the actual file, so we need to open it read/write. But, the
00165         * field in the hashp structure needs to be accurate so that
00166         * we can check accesses.
00167         */
00168        hashp->flags = flags;
00169 
00170        new_table = 0;
00171        if (!file || (flags & O_TRUNC)     || (stat(file, &statbuf)  && (errno == ENOENT))) 
00172        {
00173               if (errno == ENOENT)
00174                      errno = 0; /* Just in case someone looks at errno */
00175               new_table = 1;
00176        }
00177        else if(statbuf.st_mtime && statbuf.st_size == 0)
00178        {
00179               /* check for a zero length file and delete it
00180                * if it exists
00181                */
00182               new_table = 1;
00183        }
00184        hashp->file_size = statbuf.st_size;
00185 
00186        if (file) {                         
00187 #if defined(_WIN32) || defined(_WINDOWS) || defined (macintosh)  || defined(XP_OS2)
00188               if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1)
00189                      RETURN_ERROR(errno, error1);
00190 #else
00191               if ((hashp->fp = open(file, flags, mode)) == -1)
00192                      RETURN_ERROR(errno, error1);
00193               (void)fcntl(hashp->fp, F_SETFD, 1);
00194 #endif
00195        }
00196        if (new_table) {
00197               if (!init_hash(hashp, file, (HASHINFO *)info))
00198                      RETURN_ERROR(errno, error1);
00199        } else {
00200               /* Table already exists */
00201               if (info && info->hash)
00202                      hashp->hash = info->hash;
00203               else
00204                      hashp->hash = __default_hash;
00205 
00206               hdrsize = read(hashp->fp, (char *)&hashp->hdr, sizeof(HASHHDR));
00207               if (hdrsize == -1)
00208                      RETURN_ERROR(errno, error1);
00209               if (hdrsize != sizeof(HASHHDR))
00210                      RETURN_ERROR(EFTYPE, error1);
00211 #if BYTE_ORDER == LITTLE_ENDIAN
00212               swap_header(hashp);
00213 #endif
00214               /* Verify file type, versions and hash function */
00215               if (hashp->MAGIC != HASHMAGIC)
00216                      RETURN_ERROR(EFTYPE, error1);
00217 #define       OLDHASHVERSION       1
00218               if (hashp->VERSION != HASHVERSION &&
00219                   hashp->VERSION != OLDHASHVERSION)
00220                      RETURN_ERROR(EFTYPE, error1);
00221               if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)
00222                      RETURN_ERROR(EFTYPE, error1);
00223               if (hashp->NKEYS < 0) /* Old bad database. */
00224                      RETURN_ERROR(EFTYPE, error1);
00225 
00226               /*
00227                * Figure out how many segments we need.  Max_Bucket is the
00228                * maximum bucket number, so the number of buckets is
00229                * max_bucket + 1.
00230                */
00231               nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) /
00232                       hashp->SGSIZE;
00233               hashp->nsegs = 0;
00234               if (alloc_segs(hashp, nsegs))
00235                      /* If alloc_segs fails, errno will have been set.  */
00236                      RETURN_ERROR(errno, error1);
00237               /* Read in bitmaps */
00238               bpages = (hashp->SPARES[hashp->OVFL_POINT] +
00239                   (hashp->BSIZE << BYTE_SHIFT) - 1) >>
00240                   (hashp->BSHIFT + BYTE_SHIFT);
00241 
00242               hashp->nmaps = bpages;
00243               (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32 *));
00244        }
00245 
00246        /* Initialize Buffer Manager */
00247        if (info && info->cachesize)
00248               __buf_init(hashp, (int32) info->cachesize);
00249        else
00250               __buf_init(hashp, DEF_BUFSIZE);
00251 
00252        hashp->new_file = new_table;
00253 #ifdef macintosh
00254        hashp->save_file = file && !(hashp->flags & O_RDONLY);
00255 #else
00256        hashp->save_file = file && (hashp->flags & O_RDWR);
00257 #endif
00258        hashp->cbucket = -1;
00259        if (!(dbp = (DB *)malloc(sizeof(DB)))) {
00260               RETURN_ERROR(ENOMEM, error1);
00261        }
00262        dbp->internal = hashp;
00263        dbp->close = hash_close;
00264        dbp->del = hash_delete;
00265        dbp->fd = hash_fd;
00266        dbp->get = hash_get;
00267        dbp->put = hash_put;
00268        dbp->seq = hash_seq;
00269        dbp->sync = hash_sync;
00270        dbp->type = DB_HASH;
00271 
00272 #ifdef HASH_STATISTICS
00273        hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
00274 #endif
00275        return (dbp);
00276 
00277 error1:
00278        hdestroy(hashp);
00279        errno = save_errno;
00280        return (NULL);
00281 }
00282 
00283 static int
00284 hash_close(DB *dbp)
00285 {
00286        HTAB *hashp;
00287        int retval;
00288 
00289        if (!dbp)
00290               return (DBM_ERROR);
00291 
00292        hashp = (HTAB *)dbp->internal;
00293        if(!hashp)
00294               return (DBM_ERROR);
00295 
00296        retval = hdestroy(hashp);
00297        free(dbp);
00298        return (retval);
00299 }
00300 
00301 static int hash_fd(const DB *dbp)
00302 {
00303        HTAB *hashp;
00304 
00305        if (!dbp)
00306               return (DBM_ERROR);
00307 
00308        hashp = (HTAB *)dbp->internal;
00309        if(!hashp)
00310               return (DBM_ERROR);
00311 
00312        if (hashp->fp == -1) {
00313               errno = ENOENT;
00314               return (-1);
00315        }
00316        return (hashp->fp);
00317 }
00318 
00319 /************************** LOCAL CREATION ROUTINES **********************/
00320 static HTAB *
00321 init_hash(HTAB *hashp, const char *file, HASHINFO *info)
00322 {
00323        struct stat statbuf;
00324        int nelem;
00325 
00326        nelem = 1;
00327        hashp->NKEYS = 0;
00328        hashp->LORDER = BYTE_ORDER;
00329        hashp->BSIZE = DEF_BUCKET_SIZE;
00330        hashp->BSHIFT = DEF_BUCKET_SHIFT;
00331        hashp->SGSIZE = DEF_SEGSIZE;
00332        hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
00333        hashp->DSIZE = DEF_DIRSIZE;
00334        hashp->FFACTOR = DEF_FFACTOR;
00335        hashp->hash = __default_hash;
00336        memset(hashp->SPARES, 0, sizeof(hashp->SPARES));
00337        memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));
00338 
00339        /* Fix bucket size to be optimal for file system */
00340        if (file != NULL) {
00341               if (stat(file, &statbuf))
00342                      return (NULL);
00343 
00344 #if !defined(_WIN32) && !defined(_WINDOWS) && !defined(macintosh) && !defined(VMS) && !defined(XP_OS2)
00345 #if defined(__QNX__) && !defined(__QNXNTO__)
00346               hashp->BSIZE = 512; /* preferred blk size on qnx4 */
00347 #else
00348               hashp->BSIZE = statbuf.st_blksize;
00349 #endif
00350 
00351               /* new code added by Lou to reduce block
00352                * size down below MAX_BSIZE
00353                */
00354               if (hashp->BSIZE > MAX_BSIZE)
00355                      hashp->BSIZE = MAX_BSIZE;
00356 #endif
00357               hashp->BSHIFT = __log2((uint32)hashp->BSIZE);
00358        }
00359 
00360        if (info) {
00361               if (info->bsize) {
00362                      /* Round pagesize up to power of 2 */
00363                      hashp->BSHIFT = __log2(info->bsize);
00364                      hashp->BSIZE = 1 << hashp->BSHIFT;
00365                      if (hashp->BSIZE > MAX_BSIZE) {
00366                             errno = EINVAL;
00367                             return (NULL);
00368                      }
00369               }
00370               if (info->ffactor)
00371                      hashp->FFACTOR = info->ffactor;
00372               if (info->hash)
00373                      hashp->hash = info->hash;
00374               if (info->nelem)
00375                      nelem = info->nelem;
00376               if (info->lorder) {
00377                      if (info->lorder != BIG_ENDIAN &&
00378                          info->lorder != LITTLE_ENDIAN) {
00379                             errno = EINVAL;
00380                             return (NULL);
00381                      }
00382                      hashp->LORDER = info->lorder;
00383               }
00384        }
00385        /* init_htab sets errno if it fails */
00386        if (init_htab(hashp, nelem))
00387               return (NULL);
00388        else
00389               return (hashp);
00390 }
00391 /*
00392  * This calls alloc_segs which may run out of memory.  Alloc_segs will 
00393  * set errno, so we just pass the error information along.
00394  *
00395  * Returns 0 on No Error
00396  */
00397 static int
00398 init_htab(HTAB *hashp, int nelem)
00399 {
00400        register int nbuckets, nsegs;
00401        int l2;
00402 
00403        /*
00404         * Divide number of elements by the fill factor and determine a
00405         * desired number of buckets.  Allocate space for the next greater
00406         * power of two number of buckets.
00407         */
00408        nelem = (nelem - 1) / hashp->FFACTOR + 1;
00409 
00410        l2 = __log2((uint32)PR_MAX(nelem, 2));
00411        nbuckets = 1 << l2;
00412 
00413        hashp->SPARES[l2] = l2 + 1;
00414        hashp->SPARES[l2 + 1] = l2 + 1;
00415        hashp->OVFL_POINT = l2;
00416        hashp->LAST_FREED = 2;
00417 
00418        /* First bitmap page is at: splitpoint l2 page offset 1 */
00419        if (__ibitmap(hashp, (int)OADDR_OF(l2, 1), l2 + 1, 0))
00420               return (-1);
00421 
00422        hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
00423        hashp->HIGH_MASK = (nbuckets << 1) - 1;
00424        hashp->HDRPAGES = ((PR_MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>
00425            hashp->BSHIFT) + 1;
00426 
00427        nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
00428        nsegs = 1 << __log2((uint32)nsegs);
00429 
00430        if (nsegs > hashp->DSIZE)
00431               hashp->DSIZE = nsegs;
00432        return (alloc_segs(hashp, nsegs));
00433 }
00434 
00435 /********************** DESTROY/CLOSE ROUTINES ************************/
00436 
00437 /*
00438  * Flushes any changes to the file if necessary and destroys the hashp
00439  * structure, freeing all allocated space.
00440  */
00441 static int
00442 hdestroy(HTAB *hashp)
00443 {
00444        int i, save_errno;
00445 
00446        save_errno = 0;
00447 
00448 #ifdef HASH_STATISTICS
00449        (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
00450            hash_accesses, hash_collisions);
00451        (void)fprintf(stderr, "hdestroy: expansions %ld\n",
00452            hash_expansions);
00453        (void)fprintf(stderr, "hdestroy: overflows %ld\n",
00454            hash_overflows);
00455        (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
00456            hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
00457 
00458        for (i = 0; i < NCACHED; i++)
00459               (void)fprintf(stderr,
00460                   "spares[%d] = %d\n", i, hashp->SPARES[i]);
00461 #endif
00462        /*
00463         * Call on buffer manager to free buffers, and if required,
00464         * write them to disk.
00465         */
00466        if (__buf_free(hashp, 1, hashp->save_file))
00467               save_errno = errno;
00468        if (hashp->dir) {
00469               free(*hashp->dir);   /* Free initial segments */
00470               /* Free extra segments */
00471               while (hashp->exsegs--)
00472                      free(hashp->dir[--hashp->nsegs]);
00473               free(hashp->dir);
00474        }
00475        if (flush_meta(hashp) && !save_errno)
00476               save_errno = errno;
00477        /* Free Bigmaps */
00478        for (i = 0; i < hashp->nmaps; i++)
00479               if (hashp->mapp[i])
00480                      free(hashp->mapp[i]);
00481 
00482        if (hashp->fp != -1)
00483               (void)close(hashp->fp);
00484 
00485        if(hashp->filename) {
00486 #if defined(_WIN32) || defined(_WINDOWS) || defined(XP_OS2)
00487               if (hashp->is_temp)
00488                      (void)unlink(hashp->filename);
00489 #endif
00490               free(hashp->filename);
00491        }
00492        if (hashp->tmp_buf)
00493            free(hashp->tmp_buf);
00494        if (hashp->tmp_key)
00495            free(hashp->tmp_key);
00496        free(hashp);
00497        if (save_errno) {
00498               errno = save_errno;
00499               return (DBM_ERROR);
00500        }
00501        return (SUCCESS);
00502 }
00503 
00504 #if defined(_WIN32) || defined(_WINDOWS) 
00505 /*
00506  * Close and reopen file to force file length update on windows. 
00507  *
00508  * Returns:
00509  *      0 == OK
00510  *     -1 DBM_ERROR
00511  */
00512 static int
00513 update_EOF(HTAB *hashp)
00514 {
00515 #if defined(DBM_REOPEN_ON_FLUSH)
00516        char *      file       = hashp->filename;
00517        off_t       file_size;
00518        int         flags;
00519        int         mode       = -1;
00520        struct stat statbuf;
00521 
00522        memset(&statbuf, 0, sizeof statbuf);
00523 
00524        /* make sure we won't lose the file by closing it. */
00525        if (!file || (stat(file, &statbuf)  && (errno == ENOENT)))  {
00526               /* pretend we did it. */
00527               return 0;
00528        }
00529 
00530        (void)close(hashp->fp);
00531 
00532        flags = hashp->flags & ~(O_TRUNC | O_CREAT | O_EXCL);
00533 
00534        if ((hashp->fp = DBFILE_OPEN(file, flags | O_BINARY, mode)) == -1)
00535               return -1;
00536        file_size = lseek(hashp->fp, (off_t)0, SEEK_END);
00537        if (file_size == -1) 
00538               return -1;
00539        hashp->file_size = file_size;
00540        return 0;
00541 #else
00542        int    fd        = hashp->fp;
00543        off_t  file_size = lseek(fd, (off_t)0, SEEK_END);
00544        HANDLE handle    = (HANDLE)_get_osfhandle(fd);
00545        BOOL   cool      = FlushFileBuffers(handle);
00546 #ifdef DEBUG3
00547        if (!cool) {
00548               DWORD err = GetLastError();
00549               (void)fprintf(stderr,
00550                      "FlushFileBuffers failed, last error = %d, 0x%08x\n",
00551                      err, err);
00552        }
00553 #endif
00554        if (file_size == -1) 
00555               return -1;
00556        hashp->file_size = file_size;
00557        return cool ? 0 : -1;
00558 #endif
00559 }
00560 #endif
00561 
00562 /*
00563  * Write modified pages to disk
00564  *
00565  * Returns:
00566  *      0 == OK
00567  *     -1 DBM_ERROR
00568  */
00569 static int
00570 hash_sync(const DB *dbp, uint flags)
00571 {
00572        HTAB *hashp;
00573 
00574        if (flags != 0) {
00575               errno = EINVAL;
00576               return (DBM_ERROR);
00577        }
00578 
00579        if (!dbp)
00580               return (DBM_ERROR);
00581 
00582        hashp = (HTAB *)dbp->internal;
00583        if(!hashp)
00584               return (DBM_ERROR);
00585 
00586        if (!hashp->save_file)
00587               return (0);
00588        if (__buf_free(hashp, 0, 1) || flush_meta(hashp))
00589               return (DBM_ERROR);
00590 #if defined(_WIN32) || defined(_WINDOWS) 
00591        if (hashp->updateEOF && hashp->filename && !hashp->is_temp) {
00592               int status = update_EOF(hashp);
00593               hashp->updateEOF = 0;
00594               if (status)
00595                      return status;
00596        }
00597 #endif
00598        hashp->new_file = 0;
00599        return (0);
00600 }
00601 
00602 /*
00603  * Returns:
00604  *      0 == OK
00605  *     -1 indicates that errno should be set
00606  */
00607 static int
00608 flush_meta(HTAB *hashp)
00609 {
00610        HASHHDR *whdrp;
00611 #if BYTE_ORDER == LITTLE_ENDIAN
00612        HASHHDR whdr;
00613 #endif
00614        int fp, i, wsize;
00615 
00616        if (!hashp->save_file)
00617               return (0);
00618        hashp->MAGIC = HASHMAGIC;
00619        hashp->VERSION = HASHVERSION;
00620        hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
00621 
00622        fp = hashp->fp;
00623        whdrp = &hashp->hdr;
00624 #if BYTE_ORDER == LITTLE_ENDIAN
00625        whdrp = &whdr;
00626        swap_header_copy(&hashp->hdr, whdrp);
00627 #endif
00628        if ((lseek(fp, (off_t)0, SEEK_SET) == -1) ||
00629            ((wsize = write(fp, (char*)whdrp, sizeof(HASHHDR))) == -1))
00630               return (-1);
00631        else
00632               if (wsize != sizeof(HASHHDR)) {
00633                      errno = EFTYPE;
00634                      hashp->dbmerrno = errno;
00635                      return (-1);
00636               }
00637        for (i = 0; i < NCACHED; i++)
00638               if (hashp->mapp[i])
00639                      if (__put_page(hashp, (char *)hashp->mapp[i],
00640                             hashp->BITMAPS[i], 0, 1))
00641                             return (-1);
00642        return (0);
00643 }
00644 
00645 /*******************************SEARCH ROUTINES *****************************/
00646 /*
00647  * All the access routines return
00648  *
00649  * Returns:
00650  *      0 on SUCCESS
00651  *      1 to indicate an external DBM_ERROR (i.e. key not found, etc)
00652  *     -1 to indicate an internal DBM_ERROR (i.e. out of memory, etc)
00653  */
00654 static int
00655 hash_get(
00656        const DB *dbp,
00657        const DBT *key,
00658        DBT *data,
00659        uint flag)
00660 {
00661        HTAB *hashp;
00662        int rv;
00663 
00664        hashp = (HTAB *)dbp->internal;
00665        if (!hashp)
00666               return (DBM_ERROR);
00667 
00668        if (flag) {
00669               hashp->dbmerrno = errno = EINVAL;
00670               return (DBM_ERROR);
00671        }
00672 
00673        rv = hash_access(hashp, HASH_GET, (DBT *)key, data);
00674 
00675        if(rv == DATABASE_CORRUPTED_ERROR)
00676          {
00677 #if defined(unix) && defined(DEBUG)
00678               printf("\n\nDBM Database has been corrupted, tell Lou...\n\n");
00679 #endif
00680               __remove_database((DB *)dbp);
00681          }
00682 
00683        return(rv);
00684 }
00685 
00686 static int
00687 hash_put(
00688        const DB *dbp,
00689        DBT *key,
00690        const DBT *data,
00691        uint flag)
00692 {
00693        HTAB *hashp;
00694        int rv;
00695 
00696        hashp = (HTAB *)dbp->internal;
00697        if (!hashp)
00698               return (DBM_ERROR);
00699 
00700        if (flag && flag != R_NOOVERWRITE) {
00701               hashp->dbmerrno = errno = EINVAL;
00702               return (DBM_ERROR);
00703        }
00704        if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
00705               hashp->dbmerrno = errno = EPERM;
00706               return (DBM_ERROR);
00707        }
00708 
00709        rv =  hash_access(hashp, flag == R_NOOVERWRITE ?
00710            HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data);
00711 
00712        if(rv == DATABASE_CORRUPTED_ERROR)
00713          {
00714 #if defined(unix) && defined(DEBUG)
00715               printf("\n\nDBM Database has been corrupted, tell Lou...\n\n");
00716 #endif
00717               __remove_database((DB *)dbp);
00718          }
00719 
00720        return(rv);
00721 }
00722 
00723 static int
00724 hash_delete(
00725        const DB *dbp,
00726        const DBT *key,
00727        uint flag)           /* Ignored */
00728 {
00729        HTAB *hashp;
00730        int rv;
00731 
00732        hashp = (HTAB *)dbp->internal;
00733        if (!hashp)
00734               return (DBM_ERROR);
00735 
00736        if (flag && flag != R_CURSOR) {
00737               hashp->dbmerrno = errno = EINVAL;
00738               return (DBM_ERROR);
00739        }
00740        if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
00741               hashp->dbmerrno = errno = EPERM;
00742               return (DBM_ERROR);
00743        }
00744        rv = hash_access(hashp, HASH_DELETE, (DBT *)key, NULL);
00745 
00746        if(rv == DATABASE_CORRUPTED_ERROR)
00747          {
00748 #if defined(unix) && defined(DEBUG)
00749               printf("\n\nDBM Database has been corrupted, tell Lou...\n\n");
00750 #endif
00751               __remove_database((DB *)dbp);
00752          }
00753 
00754        return(rv);
00755 }
00756 
00757 #define MAX_OVERFLOW_HASH_ACCESS_LOOPS 2000
00758 /*
00759  * Assume that hashp has been set in wrapper routine.
00760  */
00761 static int
00762 hash_access(
00763        HTAB *hashp,
00764        ACTION action,
00765        DBT *key, DBT *val)
00766 {
00767        register BUFHEAD *rbufp;
00768        BUFHEAD *bufp, *save_bufp;
00769        register uint16 *bp;
00770        register long n, ndx, off;
00771        register size_t size;
00772        register char *kp;
00773        uint16 pageno;
00774        uint32 ovfl_loop_count=0;
00775     int32 last_overflow_page_no = -1;
00776 
00777 #ifdef HASH_STATISTICS
00778        hash_accesses++;
00779 #endif
00780 
00781        off = hashp->BSIZE;
00782        size = key->size;
00783        kp = (char *)key->data;
00784        rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);
00785        if (!rbufp)
00786               return (DATABASE_CORRUPTED_ERROR);
00787        save_bufp = rbufp;
00788 
00789        /* Pin the bucket chain */
00790        rbufp->flags |= BUF_PIN;
00791        for (bp = (uint16 *)rbufp->page, n = *bp++, ndx = 1; ndx < n;)
00792        {
00793 
00794               if (bp[1] >= REAL_KEY) {
00795                      /* Real key/data pair */
00796                      if (size == (unsigned long)(off - *bp) &&
00797                          memcmp(kp, rbufp->page + *bp, size) == 0)
00798                             goto found;
00799                      off = bp[1];
00800 #ifdef HASH_STATISTICS
00801                      hash_collisions++;
00802 #endif
00803                      bp += 2;
00804                      ndx += 2;
00805               } else if (bp[1] == OVFLPAGE) {
00806 
00807             /* database corruption: overflow loop detection */
00808             if(last_overflow_page_no == (int32)*bp)
00809                      return (DATABASE_CORRUPTED_ERROR);
00810 
00811             last_overflow_page_no = *bp;
00812 
00813                      rbufp = __get_buf(hashp, *bp, rbufp, 0);
00814                      if (!rbufp) {
00815                             save_bufp->flags &= ~BUF_PIN;
00816                             return (DBM_ERROR);
00817                      }
00818 
00819             ovfl_loop_count++;
00820             if(ovfl_loop_count > MAX_OVERFLOW_HASH_ACCESS_LOOPS)
00821                      return (DATABASE_CORRUPTED_ERROR);
00822 
00823                      /* FOR LOOP INIT */
00824                      bp = (uint16 *)rbufp->page;
00825                      n = *bp++;
00826                      ndx = 1;
00827                      off = hashp->BSIZE;
00828               } else if (bp[1] < REAL_KEY) {
00829                      if ((ndx =
00830                          __find_bigpair(hashp, rbufp, ndx, kp, (int)size)) > 0)
00831                             goto found;
00832                      if (ndx == -2) {
00833                             bufp = rbufp;
00834                             if (!(pageno =
00835                                 __find_last_page(hashp, &bufp))) {
00836                                    ndx = 0;
00837                                    rbufp = bufp;
00838                                    break; /* FOR */
00839                             }
00840                             rbufp = __get_buf(hashp, pageno, bufp, 0);
00841                             if (!rbufp) {
00842                                    save_bufp->flags &= ~BUF_PIN;
00843                                    return (DBM_ERROR);
00844                             }
00845                             /* FOR LOOP INIT */
00846                             bp = (uint16 *)rbufp->page;
00847                             n = *bp++;
00848                             ndx = 1;
00849                             off = hashp->BSIZE;
00850                      } else {
00851                             save_bufp->flags &= ~BUF_PIN;
00852                             return (DBM_ERROR);
00853 
00854                      }
00855               }
00856        }
00857 
00858        /* Not found */
00859        switch (action) {
00860        case HASH_PUT:
00861        case HASH_PUTNEW:
00862               if (__addel(hashp, rbufp, key, val)) {
00863                      save_bufp->flags &= ~BUF_PIN;
00864                      return (DBM_ERROR);
00865               } else {
00866                      save_bufp->flags &= ~BUF_PIN;
00867                      return (SUCCESS);
00868               }
00869        case HASH_GET:
00870        case HASH_DELETE:
00871        default:
00872               save_bufp->flags &= ~BUF_PIN;
00873               return (ABNORMAL);
00874        }
00875 
00876 found:
00877        switch (action) {
00878        case HASH_PUTNEW:
00879               save_bufp->flags &= ~BUF_PIN;
00880               return (ABNORMAL);
00881        case HASH_GET:
00882               bp = (uint16 *)rbufp->page;
00883               if (bp[ndx + 1] < REAL_KEY) {
00884                      if (__big_return(hashp, rbufp, ndx, val, 0))
00885                             return (DBM_ERROR);
00886               } else {
00887                      val->data = (uint8 *)rbufp->page + (int)bp[ndx + 1];
00888                      val->size = bp[ndx] - bp[ndx + 1];
00889               }
00890               break;
00891        case HASH_PUT:
00892               if ((__delpair(hashp, rbufp, ndx)) ||
00893                   (__addel(hashp, rbufp, key, val))) {
00894                      save_bufp->flags &= ~BUF_PIN;
00895                      return (DBM_ERROR);
00896               }
00897               break;
00898        case HASH_DELETE:
00899               if (__delpair(hashp, rbufp, ndx))
00900                      return (DBM_ERROR);
00901               break;
00902        default:
00903               abort();
00904        }
00905        save_bufp->flags &= ~BUF_PIN;
00906        return (SUCCESS);
00907 }
00908 
00909 static int
00910 hash_seq(
00911        const DB *dbp,
00912        DBT *key, DBT *data,
00913        uint flag)
00914 {
00915        register uint32 bucket;
00916        register BUFHEAD *bufp;
00917        HTAB *hashp;
00918        uint16 *bp, ndx;
00919 
00920        hashp = (HTAB *)dbp->internal;
00921        if (!hashp)
00922               return (DBM_ERROR);
00923 
00924        if (flag && flag != R_FIRST && flag != R_NEXT) {
00925               hashp->dbmerrno = errno = EINVAL;
00926               return (DBM_ERROR);
00927        }
00928 #ifdef HASH_STATISTICS
00929        hash_accesses++;
00930 #endif
00931        if ((hashp->cbucket < 0) || (flag == R_FIRST)) {
00932               hashp->cbucket = 0;
00933               hashp->cndx = 1;
00934               hashp->cpage = NULL;
00935        }
00936 
00937        for (bp = NULL; !bp || !bp[0]; ) {
00938               if (!(bufp = hashp->cpage)) {
00939                      for (bucket = hashp->cbucket;
00940                          bucket <= (uint32)hashp->MAX_BUCKET;
00941                          bucket++, hashp->cndx = 1) {
00942                             bufp = __get_buf(hashp, bucket, NULL, 0);
00943                             if (!bufp)
00944                                    return (DBM_ERROR);
00945                             hashp->cpage = bufp;
00946                             bp = (uint16 *)bufp->page;
00947                             if (bp[0])
00948                                    break;
00949                      }
00950                      hashp->cbucket = bucket;
00951                      if (hashp->cbucket > hashp->MAX_BUCKET) {
00952                             hashp->cbucket = -1;
00953                             return (ABNORMAL);
00954                      }
00955               } else
00956                      bp = (uint16 *)hashp->cpage->page;
00957 
00958 #ifdef DEBUG
00959               assert(bp);
00960               assert(bufp);
00961 #endif
00962               while (bp[hashp->cndx + 1] == OVFLPAGE) {
00963                      bufp = hashp->cpage =
00964                          __get_buf(hashp, bp[hashp->cndx], bufp, 0);
00965                      if (!bufp)
00966                             return (DBM_ERROR);
00967                      bp = (uint16 *)(bufp->page);
00968                      hashp->cndx = 1;
00969               }
00970               if (!bp[0]) {
00971                      hashp->cpage = NULL;
00972                      ++hashp->cbucket;
00973               }
00974        }
00975        ndx = hashp->cndx;
00976        if (bp[ndx + 1] < REAL_KEY) {
00977               if (__big_keydata(hashp, bufp, key, data, 1))
00978                      return (DBM_ERROR);
00979        } else {
00980               key->data = (uint8 *)hashp->cpage->page + bp[ndx];
00981               key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
00982               data->data = (uint8 *)hashp->cpage->page + bp[ndx + 1];
00983               data->size = bp[ndx] - bp[ndx + 1];
00984               ndx += 2;
00985               if (ndx > bp[0]) {
00986                      hashp->cpage = NULL;
00987                      hashp->cbucket++;
00988                      hashp->cndx = 1;
00989               } else
00990                      hashp->cndx = ndx;
00991        }
00992        return (SUCCESS);
00993 }
00994 
00995 /********************************* UTILITIES ************************/
00996 
00997 /*
00998  * Returns:
00999  *      0 ==> OK
01000  *     -1 ==> Error
01001  */
01002 extern int
01003 __expand_table(HTAB *hashp)
01004 {
01005        uint32 old_bucket, new_bucket;
01006        int new_segnum, spare_ndx;
01007        size_t dirsize;
01008 
01009 #ifdef HASH_STATISTICS
01010        hash_expansions++;
01011 #endif
01012        new_bucket = ++hashp->MAX_BUCKET;
01013        old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
01014 
01015        new_segnum = new_bucket >> hashp->SSHIFT;
01016 
01017        /* Check if we need a new segment */
01018        if (new_segnum >= hashp->nsegs) {
01019               /* Check if we need to expand directory */
01020               if (new_segnum >= hashp->DSIZE) {
01021                      /* Reallocate directory */
01022                      dirsize = hashp->DSIZE * sizeof(SEGMENT *);
01023                      if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))
01024                             return (-1);
01025                      hashp->DSIZE = dirsize << 1;
01026               }
01027               if ((hashp->dir[new_segnum] =
01028                   (SEGMENT)calloc((size_t)hashp->SGSIZE, sizeof(SEGMENT))) == NULL)
01029                      return (-1);
01030               hashp->exsegs++;
01031               hashp->nsegs++;
01032        }
01033        /*
01034         * If the split point is increasing (MAX_BUCKET's log base 2
01035         * * increases), we need to copy the current contents of the spare
01036         * split bucket to the next bucket.
01037         */
01038        spare_ndx = __log2((uint32)(hashp->MAX_BUCKET + 1));
01039        if (spare_ndx > hashp->OVFL_POINT) {
01040               hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
01041               hashp->OVFL_POINT = spare_ndx;
01042        }
01043 
01044        if (new_bucket > (uint32)hashp->HIGH_MASK) {
01045               /* Starting a new doubling */
01046               hashp->LOW_MASK = hashp->HIGH_MASK;
01047               hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
01048        }
01049        /* Relocate records to the new bucket */
01050        return (__split_page(hashp, old_bucket, new_bucket));
01051 }
01052 
01053 /*
01054  * If realloc guarantees that the pointer is not destroyed if the realloc
01055  * fails, then this routine can go away.
01056  */
01057 static void *
01058 hash_realloc(
01059        SEGMENT **p_ptr,
01060        size_t oldsize, size_t newsize)
01061 {
01062        register void *p;
01063 
01064        if ((p = malloc(newsize))) {
01065               memmove(p, *p_ptr, oldsize);
01066               memset((char *)p + oldsize, 0, newsize - oldsize);
01067               free(*p_ptr);
01068               *p_ptr = (SEGMENT *)p;
01069        }
01070        return (p);
01071 }
01072 
01073 extern uint32
01074 __call_hash(HTAB *hashp, char *k, size_t len)
01075 {
01076        uint32 n, bucket;
01077 
01078        n = hashp->hash(k, len);
01079        bucket = n & hashp->HIGH_MASK;
01080        if (bucket > (uint32)hashp->MAX_BUCKET)
01081               bucket = bucket & hashp->LOW_MASK;
01082        return (bucket);
01083 }
01084 
01085 /*
01086  * Allocate segment table.  On error, set errno.
01087  *
01088  * Returns 0 on success
01089  */
01090 static int
01091 alloc_segs(
01092        HTAB *hashp,
01093        int nsegs)
01094 {
01095        register int i;
01096        register SEGMENT store;
01097 
01098        if ((hashp->dir =
01099            (SEGMENT *)calloc((size_t)hashp->DSIZE, sizeof(SEGMENT *))) == NULL) {
01100               errno = ENOMEM;
01101               return (-1);
01102        }
01103        /* Allocate segments */
01104        if ((store =
01105            (SEGMENT)calloc((size_t)nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {
01106               errno = ENOMEM;
01107               return (-1);
01108        }
01109        for (i = 0; i < nsegs; i++, hashp->nsegs++)
01110               hashp->dir[i] = &store[i << hashp->SSHIFT];
01111        return (0);
01112 }
01113 
01114 #if BYTE_ORDER == LITTLE_ENDIAN
01115 /*
01116  * Hashp->hdr needs to be byteswapped.
01117  */
01118 static void
01119 swap_header_copy(
01120        HASHHDR *srcp, HASHHDR *destp)
01121 {
01122        int i;
01123 
01124        P_32_COPY(srcp->magic, destp->magic);
01125        P_32_COPY(srcp->version, destp->version);
01126        P_32_COPY(srcp->lorder, destp->lorder);
01127        P_32_COPY(srcp->bsize, destp->bsize);
01128        P_32_COPY(srcp->bshift, destp->bshift);
01129        P_32_COPY(srcp->dsize, destp->dsize);
01130        P_32_COPY(srcp->ssize, destp->ssize);
01131        P_32_COPY(srcp->sshift, destp->sshift);
01132        P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
01133        P_32_COPY(srcp->last_freed, destp->last_freed);
01134        P_32_COPY(srcp->max_bucket, destp->max_bucket);
01135        P_32_COPY(srcp->high_mask, destp->high_mask);
01136        P_32_COPY(srcp->low_mask, destp->low_mask);
01137        P_32_COPY(srcp->ffactor, destp->ffactor);
01138        P_32_COPY(srcp->nkeys, destp->nkeys);
01139        P_32_COPY(srcp->hdrpages, destp->hdrpages);
01140        P_32_COPY(srcp->h_charkey, destp->h_charkey);
01141        for (i = 0; i < NCACHED; i++) {
01142               P_32_COPY(srcp->spares[i], destp->spares[i]);
01143               P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
01144        }
01145 }
01146 
01147 static void
01148 swap_header(HTAB *hashp)
01149 {
01150        HASHHDR *hdrp;
01151        int i;
01152 
01153        hdrp = &hashp->hdr;
01154 
01155        M_32_SWAP(hdrp->magic);
01156        M_32_SWAP(hdrp->version);
01157        M_32_SWAP(hdrp->lorder);
01158        M_32_SWAP(hdrp->bsize);
01159        M_32_SWAP(hdrp->bshift);
01160        M_32_SWAP(hdrp->dsize);
01161        M_32_SWAP(hdrp->ssize);
01162        M_32_SWAP(hdrp->sshift);
01163        M_32_SWAP(hdrp->ovfl_point);
01164        M_32_SWAP(hdrp->last_freed);
01165        M_32_SWAP(hdrp->max_bucket);
01166        M_32_SWAP(hdrp->high_mask);
01167        M_32_SWAP(hdrp->low_mask);
01168        M_32_SWAP(hdrp->ffactor);
01169        M_32_SWAP(hdrp->nkeys);
01170        M_32_SWAP(hdrp->hdrpages);
01171        M_32_SWAP(hdrp->h_charkey);
01172        for (i = 0; i < NCACHED; i++) {
01173               M_32_SWAP(hdrp->spares[i]);
01174               M_16_SWAP(hdrp->bitmaps[i]);
01175        }
01176 }
01177 #endif