Subversion Repositories openrisc

/*-

 * Copyright (c) 1990, 1993, 1994

 *      The Regents of the University of California.  All rights reserved.

 *

 * This code is derived from software contributed to Berkeley by

 * Margo Seltzer.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 * 3. All advertising materials mentioning features or use of this software

 *    must display the following acknowledgement:

 *      This product includes software developed by the University of

 *      California, Berkeley and its contributors.

 * 4. Neither the name of the University nor the names of its contributors

 *    may be used to endorse or promote products derived from this software

 *    without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 * SUCH DAMAGE.

 */

#include <sys/param.h>

#if defined(LIBC_SCCS) && !defined(lint)

static char sccsid[] = "@(#)hash.c      8.9 (Berkeley) 6/16/94";

#endif /* LIBC_SCCS and not lint */

#include <sys/cdefs.h>

#include <sys/types.h>

#include <sys/stat.h>

#include <errno.h>

#include <fcntl.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#ifdef DEBUG

#include <assert.h>

#endif

#include "db_local.h"

#include "hash.h"

#include "page.h"

#include "extern.h"

static int   alloc_segs(HTAB *, int);

static int   flush_meta(HTAB *);

static int   hash_access(HTAB *, ACTION, DBT *, DBT *);

static int   hash_close(DB *);

static int   hash_delete(const DB *, const DBT *, __uint32_t);

static int   hash_fd(const DB *);

static int   hash_get(const DB *, const DBT *, DBT *, __uint32_t);

static int   hash_put(const DB *, DBT *, const DBT *, __uint32_t);

static void *hash_realloc(SEGMENT **, int, int);

static int   hash_seq(const DB *, DBT *, DBT *, __uint32_t);

static int   hash_sync(const DB *, __uint32_t);

static int   hdestroy(HTAB *);

static HTAB *init_hash(HTAB *, const char *, const HASHINFO *);

static int   init_htab(HTAB *, int);

#if (BYTE_ORDER == LITTLE_ENDIAN)

static void  swap_header(HTAB *);

static void  swap_header_copy(HASHHDR *, HASHHDR *);

#endif

/* Macros for min/max.  */

#ifndef MIN

#define MIN(a,b) (((a)<(b))?(a):(b))

#endif

#ifndef MAX

#define MAX(a,b) (((a)>(b))?(a):(b))

#endif

/* Fast arithmetic, relying on powers of 2, */

#define MOD(x, y)               ((x) & ((y) - 1))

#define RETURN_ERROR(ERR, LOC)  { save_errno = ERR; goto LOC; }

/* Return values */

#define SUCCESS  (0)

#define ERROR   (-1)

#define ABNORMAL (1)

#ifdef HASH_STATISTICS

int hash_accesses, hash_collisions, hash_expansions, hash_overflows;

#endif

/************************** INTERFACE ROUTINES ***************************/

/* OPEN/CLOSE */

extern DB *

__hash_open(file, flags, mode, info, dflags)

        const char *file;

        int flags, mode, dflags;

        const HASHINFO *info;   /* Special directives for create */

{

        HTAB *hashp;

#ifdef __USE_INTERNAL_STAT64

        struct stat64 statbuf;

#else

        struct stat statbuf;

#endif

        DB *dbp;

        int bpages, hdrsize, new_table, nsegs, save_errno;

        if ((flags & O_ACCMODE) == O_WRONLY) {

                errno = EINVAL;

                return (NULL);

        }

        if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))

                return (NULL);

        hashp->fp = -1;

        /*

         * Even if user wants write only, we need to be able to read

         * the actual file, so we need to open it read/write. But, the

         * field in the hashp structure needs to be accurate so that

         * we can check accesses.

         */

        hashp->flags = flags;

        new_table = 0;

        if (!file || (flags & O_TRUNC) ||

#ifdef __USE_INTERNAL_STAT64

            (stat64(file, &statbuf) && (errno == ENOENT))) {

#else

            (stat(file, &statbuf) && (errno == ENOENT))) {

#endif

                if (errno == ENOENT)

                        errno = 0; /* Just in case someone looks at errno */

                new_table = 1;

        }

        if (file) {

                if ((hashp->fp = open(file, flags, mode)) == -1)

                        RETURN_ERROR(errno, error0);

                /* if the .db file is empty, and we had permission to create

                   a new .db file, then reinitialize the database */

                if ((flags & O_CREAT) &&

#ifdef __USE_INTERNAL_STAT64

                     fstat64(hashp->fp, &statbuf) == 0 && statbuf.st_size == 0)

#else

                     fstat(hashp->fp, &statbuf) == 0 && statbuf.st_size == 0)

#endif

                        new_table = 1;

#ifdef HAVE_FCNTL

                (void)fcntl(hashp->fp, F_SETFD, 1);

#endif

        }

        if (new_table) {

                if (!(hashp = init_hash(hashp, file, (HASHINFO *)info)))

                        RETURN_ERROR(errno, error1);

        } else {

                /* Table already exists */

                if (info && info->hash)

                        hashp->hash = info->hash;

                else

                        hashp->hash = __default_hash;

                hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR));

#if (BYTE_ORDER == LITTLE_ENDIAN)

                swap_header(hashp);

#endif

                if (hdrsize == -1)

                        RETURN_ERROR(errno, error1);

                if (hdrsize != sizeof(HASHHDR))

                        RETURN_ERROR(EFTYPE, error1);

                /* Verify file type, versions and hash function */

                if (hashp->MAGIC != HASHMAGIC)

                        RETURN_ERROR(EFTYPE, error1);

#define OLDHASHVERSION  1

                if (hashp->HASH_VERSION != HASHVERSION &&

                    hashp->HASH_VERSION != OLDHASHVERSION)

                        RETURN_ERROR(EFTYPE, error1);

                if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)

                        RETURN_ERROR(EFTYPE, error1);

                /*

                 * Figure out how many segments we need.  Max_Bucket is the

                 * maximum bucket number, so the number of buckets is

                 * max_bucket + 1.

                 */

                nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) /

                         hashp->SGSIZE;

                hashp->nsegs = 0;

                if (alloc_segs(hashp, nsegs))

                        /*

                         * If alloc_segs fails, table will have been destroyed

                         * and errno will have been set.

                         */

                        return (NULL);

                /* Read in bitmaps */

                bpages = (hashp->SPARES[hashp->OVFL_POINT] +

                    (hashp->BSIZE << BYTE_SHIFT) - 1) >>

                    (hashp->BSHIFT + BYTE_SHIFT);

                hashp->nmaps = bpages;

                (void)memset(&hashp->mapp[0], 0, bpages * sizeof(__uint32_t *));

        }

        /* Initialize Buffer Manager */

        if (info && info->cachesize)

                __buf_init(hashp, info->cachesize);

        else

                __buf_init(hashp, DEF_BUFSIZE);

        hashp->new_file = new_table;

        hashp->save_file = file && (hashp->flags & O_RDWR);

        hashp->cbucket = -1;

        if (!(dbp = (DB *)malloc(sizeof(DB)))) {

                save_errno = errno;

                hdestroy(hashp);

                errno = save_errno;

                return (NULL);

        }

        dbp->internal = hashp;

        dbp->close = hash_close;

        dbp->del = hash_delete;

        dbp->fd = hash_fd;

        dbp->get = hash_get;

        dbp->put = hash_put;

        dbp->seq = hash_seq;

        dbp->sync = hash_sync;

        dbp->type = DB_HASH;

#ifdef DEBUG

        (void)fprintf(stderr,

"%s\n%s%x\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",

            "init_htab:",

            "TABLE POINTER   ", hashp,

            "BUCKET SIZE     ", hashp->BSIZE,

            "BUCKET SHIFT    ", hashp->BSHIFT,

            "DIRECTORY SIZE  ", hashp->DSIZE,

            "SEGMENT SIZE    ", hashp->SGSIZE,

            "SEGMENT SHIFT   ", hashp->SSHIFT,

            "FILL FACTOR     ", hashp->FFACTOR,

            "MAX BUCKET      ", hashp->MAX_BUCKET,

            "OVFL POINT      ", hashp->OVFL_POINT,

            "LAST FREED      ", hashp->LAST_FREED,

            "HIGH MASK       ", hashp->HIGH_MASK,

            "LOW  MASK       ", hashp->LOW_MASK,

            "NSEGS           ", hashp->nsegs,

            "NKEYS           ", hashp->NKEYS);

#endif

#ifdef HASH_STATISTICS

        hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;

#endif

        return (dbp);

error1:

        if (hashp != NULL)

                (void)close(hashp->fp);

error0:

        free(hashp);

        errno = save_errno;

        return (NULL);

}

static int

hash_close(dbp)

        DB *dbp;

{

        HTAB *hashp;

        int retval;

        if (!dbp)

                return (ERROR);

        hashp = (HTAB *)dbp->internal;

        retval = hdestroy(hashp);

        free(dbp);

        return (retval);

}

static int

hash_fd(dbp)

        const DB *dbp;

{

        HTAB *hashp;

        if (!dbp)

                return (ERROR);

        hashp = (HTAB *)dbp->internal;

        if (hashp->fp == -1) {

                errno = ENOENT;

                return (-1);

        }

        return (hashp->fp);

}

/************************** LOCAL CREATION ROUTINES **********************/

static HTAB *

init_hash(hashp, file, info)

        HTAB *hashp;

        const char *file;

        const HASHINFO *info;

{

        struct stat statbuf;

        int nelem;

        nelem = 1;

        hashp->NKEYS = 0;

       hashp->LORDER = DB_BYTE_ORDER;

        hashp->BSIZE = DEF_BUCKET_SIZE;

        hashp->BSHIFT = DEF_BUCKET_SHIFT;

        hashp->SGSIZE = DEF_SEGSIZE;

        hashp->SSHIFT = DEF_SEGSIZE_SHIFT;

        hashp->DSIZE = DEF_DIRSIZE;

        hashp->FFACTOR = DEF_FFACTOR;

        hashp->hash = __default_hash;

        memset(hashp->SPARES, 0, sizeof(hashp->SPARES));

        memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));

        /* Fix bucket size to be optimal for file system */

        if (file != NULL) {

#ifdef __USE_INTERNAL_STAT64

                if (stat64(file, &statbuf))

#else

                if (stat(file, &statbuf))

#endif

                        return (NULL);

                hashp->BSIZE = statbuf.st_blksize;

                hashp->BSHIFT = __log2(hashp->BSIZE);

        }

        if (info) {

                if (info->bsize) {

                        /* Round pagesize up to power of 2 */

                        hashp->BSHIFT = __log2(info->bsize);

                        hashp->BSIZE = 1 << hashp->BSHIFT;

                        if (hashp->BSIZE > MAX_BSIZE) {

                                errno = EINVAL;

                                return (NULL);

                        }

                }

                if (info->ffactor)

                        hashp->FFACTOR = info->ffactor;

                if (info->hash)

                        hashp->hash = info->hash;

                if (info->nelem)

                        nelem = info->nelem;

                if (info->lorder) {

                       if (info->lorder != DB_BIG_ENDIAN &&

                           info->lorder != DB_LITTLE_ENDIAN) {

                                errno = EINVAL;

                                return (NULL);

                        }

                        hashp->LORDER = info->lorder;

                }

        }

        /* init_htab should destroy the table and set errno if it fails */

        if (init_htab(hashp, nelem))

                return (NULL);

        else

                return (hashp);

}

/*

 * This calls alloc_segs which may run out of memory.  Alloc_segs will destroy

 * the table and set errno, so we just pass the error information along.

 *

 * Returns 0 on No Error

 */

static int

init_htab(hashp, nelem)

        HTAB *hashp;

        int nelem;

{

        int nbuckets, nsegs;

        int l2;

        /*

         * Divide number of elements by the fill factor and determine a

         * desired number of buckets.  Allocate space for the next greater

         * power of two number of buckets.

         */

        nelem = (nelem - 1) / hashp->FFACTOR + 1;

        l2 = __log2(MAX(nelem, 2));

        nbuckets = 1 << l2;

        hashp->SPARES[l2] = l2 + 1;

        hashp->SPARES[l2 + 1] = l2 + 1;

        hashp->OVFL_POINT = l2;

        hashp->LAST_FREED = 2;

        /* First bitmap page is at: splitpoint l2 page offset 1 */

        if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))

                return (-1);

        hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;

        hashp->HIGH_MASK = (nbuckets << 1) - 1;

        hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>

            hashp->BSHIFT) + 1;

        nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;

        nsegs = 1 << __log2(nsegs);

        if (nsegs > hashp->DSIZE)

                hashp->DSIZE = nsegs;

        return (alloc_segs(hashp, nsegs));

}

/********************** DESTROY/CLOSE ROUTINES ************************/

/*

 * Flushes any changes to the file if necessary and destroys the hashp

 * structure, freeing all allocated space.

 */

static int

hdestroy(hashp)

        HTAB *hashp;

{

        int i, save_errno;

        save_errno = 0;

#ifdef HASH_STATISTICS

        (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",

            hash_accesses, hash_collisions);

        (void)fprintf(stderr, "hdestroy: expansions %ld\n",

            hash_expansions);

        (void)fprintf(stderr, "hdestroy: overflows %ld\n",

            hash_overflows);

        (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",

            hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);

        for (i = 0; i < NCACHED; i++)

                (void)fprintf(stderr,

                    "spares[%d] = %d\n", i, hashp->SPARES[i]);

#endif

        /*

         * Call on buffer manager to free buffers, and if required,

         * write them to disk.

         */

        if (__buf_free(hashp, 1, hashp->save_file))

                save_errno = errno;

        if (hashp->dir) {

                free(*hashp->dir);      /* Free initial segments */

                /* Free extra segments */

                while (hashp->exsegs--)

                        free(hashp->dir[--hashp->nsegs]);

                free(hashp->dir);

        }

        if (flush_meta(hashp) && !save_errno)

                save_errno = errno;

        /* Free Bigmaps */

        for (i = 0; i < hashp->nmaps; i++)

                if (hashp->mapp[i])

                        free(hashp->mapp[i]);

        if (hashp->fp != -1)

                (void)close(hashp->fp);

        free(hashp);

        if (save_errno) {

                errno = save_errno;

                return (ERROR);

        }

        return (SUCCESS);

}

/*

 * Write modified pages to disk

 *

 * Returns:

 *       0 == OK

 *      -1 ERROR

 */

static int

hash_sync(dbp, flags)

        const DB *dbp;

        __uint32_t flags;

{

        HTAB *hashp;

        if (flags != 0) {

                errno = EINVAL;

                return (ERROR);

        }

        if (!dbp)

                return (ERROR);

        hashp = (HTAB *)dbp->internal;

        if (!hashp->save_file)

                return (0);

        if (__buf_free(hashp, 0, 1) || flush_meta(hashp))

                return (ERROR);

        hashp->new_file = 0;

        return (0);

}

/*

 * Returns:

 *       0 == OK

 *      -1 indicates that errno should be set

 */

static int

flush_meta(hashp)

        HTAB *hashp;

{

        HASHHDR *whdrp;

#if (BYTE_ORDER == LITTLE_ENDIAN)

        HASHHDR whdr;

#endif

        int fp, i, wsize;

        if (!hashp->save_file)

                return (0);

        hashp->MAGIC = HASHMAGIC;

        hashp->HASH_VERSION = HASHVERSION;

        hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));

        fp = hashp->fp;

        whdrp = &hashp->hdr;

#if (BYTE_ORDER == LITTLE_ENDIAN)

        whdrp = &whdr;

        swap_header_copy(&hashp->hdr, whdrp);

#endif

        if ((lseek(fp, (off_t)0, SEEK_SET) == -1) ||

            ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1))

                return (-1);

        else

                if (wsize != sizeof(HASHHDR)) {

                        errno = EFTYPE;

                        hashp->error = errno;

                        return (-1);

                }

        for (i = 0; i < NCACHED; i++)

                if (hashp->mapp[i])

                        if (__put_page(hashp, (char *)hashp->mapp[i],

                                hashp->BITMAPS[i], 0, 1))

                                return (-1);

        return (0);

}

/*******************************SEARCH ROUTINES *****************************/

/*

 * All the access routines return

 *

 * Returns:

 *       0 on SUCCESS

 *       1 to indicate an external ERROR (i.e. key not found, etc)

 *      -1 to indicate an internal ERROR (i.e. out of memory, etc)

 */

static int

hash_get(dbp, key, data, flag)

        const DB *dbp;

        const DBT *key;

        DBT *data;

        __uint32_t flag;

{

        HTAB *hashp;

        hashp = (HTAB *)dbp->internal;

        if (flag) {

                hashp->error = errno = EINVAL;

                return (ERROR);

        }

        return (hash_access(hashp, HASH_GET, (DBT *)key, data));

}

static int

hash_put(dbp, key, data, flag)

        const DB *dbp;

        DBT *key;

        const DBT *data;

        __uint32_t flag;

{

        HTAB *hashp;

        hashp = (HTAB *)dbp->internal;

        if (flag && flag != R_NOOVERWRITE) {

                hashp->error = EINVAL;

                errno = EINVAL;

                return (ERROR);

        }

        if ((hashp->flags & O_ACCMODE) == O_RDONLY) {

                hashp->error = errno = EPERM;

                return (ERROR);

        }

        return (hash_access(hashp, flag == R_NOOVERWRITE ?

            HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data));

}

static int

hash_delete(dbp, key, flag)

        const DB *dbp;

        const DBT *key;

        __uint32_t flag;                /* Ignored */

{

        HTAB *hashp;

        hashp = (HTAB *)dbp->internal;

        if (flag && flag != R_CURSOR) {

                hashp->error = errno = EINVAL;

                return (ERROR);

        }

        if ((hashp->flags & O_ACCMODE) == O_RDONLY) {

                hashp->error = errno = EPERM;

                return (ERROR);

        }

        return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));

}

/*

 * Assume that hashp has been set in wrapper routine.

 */

static int

hash_access(hashp, action, key, val)

        HTAB *hashp;

        ACTION action;

        DBT *key, *val;

{

        BUFHEAD *rbufp;

        BUFHEAD *bufp, *save_bufp;

        __uint16_t *bp;

        int n, ndx, off, size;

        char *kp;

        __uint16_t pageno;

#ifdef HASH_STATISTICS

        hash_accesses++;

#endif

        off = hashp->BSIZE;

        size = key->size;

        kp = (char *)key->data;

        rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);

        if (!rbufp)

                return (ERROR);

        save_bufp = rbufp;

        /* Pin the bucket chain */

        rbufp->flags |= BUF_PIN;

        for (bp = (__uint16_t *)rbufp->page, n = *bp++, ndx = 1; ndx < n;)

                if (bp[1] >= REAL_KEY) {

                        /* Real key/data pair */

                        if (size == off - *bp &&