Subversion Repositories scarts

/*-

 * 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_page.c 8.7 (Berkeley) 8/16/94";

#endif /* LIBC_SCCS and not lint */

#include <sys/cdefs.h>

/*

 * PACKAGE:  hashing

 *

 * DESCRIPTION:

 *      Page manipulation for hashing package.

 *

 * ROUTINES:

 *

 * External

 *      __get_page

 *      __add_ovflpage

 * Internal

 *      overflow_page

 *      open_temp

 */

#include <sys/types.h>

#include <errno.h>

#include <fcntl.h>

#include <signal.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 __uint32_t       *fetch_bitmap(HTAB *, int);

static __uint32_t        first_free(__uint32_t);

static int       open_temp(HTAB *);

static __uint16_t        overflow_page(HTAB *);

static void      putpair(char *, const DBT *, const DBT *);

static void      squeeze_key(__uint16_t *, const DBT *, const DBT *);

static int       ugly_split

(HTAB *, __uint32_t, BUFHEAD *, BUFHEAD *, int, int);

#define PAGE_INIT(P) { \

        ((__uint16_t *)(P))[0] = 0; \

        ((__uint16_t *)(P))[1] = hashp->BSIZE - 3 * sizeof(__uint16_t); \

        ((__uint16_t *)(P))[2] = hashp->BSIZE; \

}

/*

 * This is called AFTER we have verified that there is room on the page for

 * the pair (PAIRFITS has returned true) so we go right ahead and start moving

 * stuff on.

 */

static void

putpair(p, key, val)

        char *p;

        const DBT *key, *val;

{

        __uint16_t *bp, n, off;

        bp = (__uint16_t *)p;

        /* Enter the key first. */

        n = bp[0];

        off = OFFSET(bp) - key->size;

        memmove(p + off, key->data, key->size);

        bp[++n] = off;

        /* Now the data. */

        off -= val->size;

        memmove(p + off, val->data, val->size);

        bp[++n] = off;

        /* Adjust page info. */

        bp[0] = n;

        bp[n + 1] = off - ((n + 3) * sizeof(__uint16_t));

        bp[n + 2] = off;

}

/*

 * Returns:

 *       0 OK

 *      -1 error

 */

extern int

__delpair(hashp, bufp, ndx)

        HTAB *hashp;

        BUFHEAD *bufp;

        int ndx;

{

        __uint16_t *bp, newoff;

        int n;

        __uint16_t pairlen;

        bp = (__uint16_t *)bufp->page;

        n = bp[0];

        if (bp[ndx + 1] < REAL_KEY)

                return (__big_delete(hashp, bufp));

        if (ndx != 1)

                newoff = bp[ndx - 1];

        else

                newoff = hashp->BSIZE;

        pairlen = newoff - bp[ndx + 1];

        if (ndx != (n - 1)) {

                /* Hard Case -- need to shuffle keys */

                int i;

                char *src = bufp->page + (int)OFFSET(bp);

                char *dst = src + (int)pairlen;

                memmove(dst, src, bp[ndx + 1] - OFFSET(bp));

                /* Now adjust the pointers */

                for (i = ndx + 2; i <= n; i += 2) {

                        if (bp[i + 1] == OVFLPAGE) {

                                bp[i - 2] = bp[i];

                                bp[i - 1] = bp[i + 1];

                        } else {

                                bp[i - 2] = bp[i] + pairlen;

                                bp[i - 1] = bp[i + 1] + pairlen;

                        }

                }

        }

        /* Finally adjust the page data */

        bp[n] = OFFSET(bp) + pairlen;

        bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(__uint16_t);

        bp[0] = n - 2;

        hashp->NKEYS--;

        bufp->flags |= BUF_MOD;

        return (0);

}

/*

 * Returns:

 *       0 ==> OK

 *      -1 ==> Error

 */

extern int

__split_page(hashp, obucket, nbucket)

        HTAB *hashp;

        __uint32_t obucket, nbucket;

{

        BUFHEAD *new_bufp, *old_bufp;

        __uint16_t *ino;

        char *np;

        DBT key, val;

        int n, ndx, retval;

        __uint16_t copyto, diff, off, moved;

        char *op;

        copyto = (__uint16_t)hashp->BSIZE;

        off = (__uint16_t)hashp->BSIZE;

        old_bufp = __get_buf(hashp, obucket, NULL, 0);

        if (old_bufp == NULL)

                return (-1);

        new_bufp = __get_buf(hashp, nbucket, NULL, 0);

        if (new_bufp == NULL)

                return (-1);

        old_bufp->flags |= (BUF_MOD | BUF_PIN);

        new_bufp->flags |= (BUF_MOD | BUF_PIN);

        ino = (__uint16_t *)(op = old_bufp->page);

        np = new_bufp->page;

        moved = 0;

        for (n = 1, ndx = 1; n < ino[0]; n += 2) {

                if (ino[n + 1] < REAL_KEY) {

                        retval = ugly_split(hashp, obucket, old_bufp, new_bufp,

                            (int)copyto, (int)moved);

                        old_bufp->flags &= ~BUF_PIN;

                        new_bufp->flags &= ~BUF_PIN;

                        return (retval);

                }

                key.data = (u_char *)op + ino[n];

                key.size = off - ino[n];

                if (__call_hash(hashp, key.data, key.size) == obucket) {

                        /* Don't switch page */

                        diff = copyto - off;

                        if (diff) {

                                copyto = ino[n + 1] + diff;

                                memmove(op + copyto, op + ino[n + 1],

                                    off - ino[n + 1]);

                                ino[ndx] = copyto + ino[n] - ino[n + 1];

                                ino[ndx + 1] = copyto;

                        } else

                                copyto = ino[n + 1];

                        ndx += 2;

                } else {

                        /* Switch page */

                        val.data = (u_char *)op + ino[n + 1];

                        val.size = ino[n] - ino[n + 1];

                        putpair(np, &key, &val);

                        moved += 2;

                }

                off = ino[n + 1];

        }

        /* Now clean up the page */

        ino[0] -= moved;

        FREESPACE(ino) = copyto - sizeof(__uint16_t) * (ino[0] + 3);

        OFFSET(ino) = copyto;

#ifdef DEBUG3

        (void)fprintf(stderr, "split %d/%d\n",

            ((__uint16_t *)np)[0] / 2,

            ((__uint16_t *)op)[0] / 2);

#endif

        /* unpin both pages */

        old_bufp->flags &= ~BUF_PIN;

        new_bufp->flags &= ~BUF_PIN;

        return (0);

}

/*

 * Called when we encounter an overflow or big key/data page during split

 * handling.  This is special cased since we have to begin checking whether

 * the key/data pairs fit on their respective pages and because we may need

 * overflow pages for both the old and new pages.

 *

 * The first page might be a page with regular key/data pairs in which case

 * we have a regular overflow condition and just need to go on to the next

 * page or it might be a big key/data pair in which case we need to fix the

 * big key/data pair.

 *

 * Returns:

 *       0 ==> success

 *      -1 ==> failure

 */

static int

ugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved)

        HTAB *hashp;

        __uint32_t obucket;     /* Same as __split_page. */

        BUFHEAD *old_bufp, *new_bufp;

        int copyto;     /* First byte on page which contains key/data values. */

        int moved;              /* Number of pairs moved to new page. */

{

        BUFHEAD *bufp;          /* Buffer header for ino */

        __uint16_t *ino;                /* Page keys come off of */

        __uint16_t *np;         /* New page */

        __uint16_t *op;         /* Page keys go on to if they aren't moving */

        BUFHEAD *last_bfp;      /* Last buf header OVFL needing to be freed */

        DBT key, val;

        SPLIT_RETURN ret;

        __uint16_t n, off, ov_addr, scopyto;

        char *cino;             /* Character value of ino */

        bufp = old_bufp;

        ino = (__uint16_t *)old_bufp->page;

        np = (__uint16_t *)new_bufp->page;

        op = (__uint16_t *)old_bufp->page;

        last_bfp = NULL;

        scopyto = (__uint16_t)copyto;   /* ANSI */

        n = ino[0] - 1;

        while (n < ino[0]) {

                if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) {

                        if (__big_split(hashp, old_bufp,

                            new_bufp, bufp, bufp->addr, obucket, &ret))

                                return (-1);

                        old_bufp = ret.oldp;

                        if (!old_bufp)

                                return (-1);

                        op = (__uint16_t *)old_bufp->page;

                        new_bufp = ret.newp;

                        if (!new_bufp)

                                return (-1);

                        np = (__uint16_t *)new_bufp->page;

                        bufp = ret.nextp;

                        if (!bufp)

                                return (0);

                        cino = (char *)bufp->page;

                        ino = (__uint16_t *)cino;

                        last_bfp = ret.nextp;

                } else if (ino[n + 1] == OVFLPAGE) {

                        ov_addr = ino[n];

                        /*

                         * Fix up the old page -- the extra 2 are the fields

                         * which contained the overflow information.

                         */

                        ino[0] -= (moved + 2);

                        FREESPACE(ino) =

                            scopyto - sizeof(__uint16_t) * (ino[0] + 3);

                        OFFSET(ino) = scopyto;

                        bufp = __get_buf(hashp, ov_addr, bufp, 0);

                        if (!bufp)

                                return (-1);

                        ino = (__uint16_t *)bufp->page;

                        n = 1;

                        scopyto = hashp->BSIZE;

                        moved = 0;

                        if (last_bfp)

                                __free_ovflpage(hashp, last_bfp);

                        last_bfp = bufp;

                }

                /* Move regular sized pairs of there are any */

                off = hashp->BSIZE;

                for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) {

                        cino = (char *)ino;

                        key.data = (u_char *)cino + ino[n];

                        key.size = off - ino[n];

                        val.data = (u_char *)cino + ino[n + 1];

                        val.size = ino[n] - ino[n + 1];

                        off = ino[n + 1];

                        if (__call_hash(hashp, key.data, key.size) == obucket) {

                                /* Keep on old page */

                                if (PAIRFITS(op, (&key), (&val)))

                                        putpair((char *)op, &key, &val);

                                else {

                                        old_bufp =

                                            __add_ovflpage(hashp, old_bufp);

                                        if (!old_bufp)

                                                return (-1);

                                        op = (__uint16_t *)old_bufp->page;

                                        putpair((char *)op, &key, &val);

                                }

                                old_bufp->flags |= BUF_MOD;

                        } else {

                                /* Move to new page */

                                if (PAIRFITS(np, (&key), (&val)))

                                        putpair((char *)np, &key, &val);

                                else {

                                        new_bufp =

                                            __add_ovflpage(hashp, new_bufp);

                                        if (!new_bufp)

                                                return (-1);

                                        np = (__uint16_t *)new_bufp->page;

                                        putpair((char *)np, &key, &val);

                                }

                                new_bufp->flags |= BUF_MOD;

                        }

                }

        }

        if (last_bfp)

                __free_ovflpage(hashp, last_bfp);

        return (0);

}

/*

 * Add the given pair to the page

 *

 * Returns:

 *      0 ==> OK

 *      1 ==> failure

 */

extern int

__addel(hashp, bufp, key, val)

        HTAB *hashp;

        BUFHEAD *bufp;

        const DBT *key, *val;

{

        __uint16_t *bp, *sop;

        int do_expand;

        bp = (__uint16_t *)bufp->page;

        do_expand = 0;

        while (bp[0] && (bp[2] < REAL_KEY || bp[bp[0]] < REAL_KEY))

                /* Exception case */

                if (bp[2] == FULL_KEY_DATA && bp[0] == 2)

                        /* This is the last page of a big key/data pair

                           and we need to add another page */

                        break;

                else if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) {

                        bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);

                        if (!bufp)

                                return (-1);

                        bp = (__uint16_t *)bufp->page;

                } else

                        /* Try to squeeze key on this page */

                        if (FREESPACE(bp) > PAIRSIZE(key, val)) {

                                squeeze_key(bp, key, val);

                                return (0);

                        } else {

                                bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);

                                if (!bufp)

                                        return (-1);

                                bp = (__uint16_t *)bufp->page;

                        }

        if (PAIRFITS(bp, key, val))

                putpair(bufp->page, key, val);

        else {

                do_expand = 1;

                bufp = __add_ovflpage(hashp, bufp);

                if (!bufp)

                        return (-1);

                sop = (__uint16_t *)bufp->page;

                if (PAIRFITS(sop, key, val))

                        putpair((char *)sop, key, val);

                else

                        if (__big_insert(hashp, bufp, key, val))

                                return (-1);

        }

        bufp->flags |= BUF_MOD;

        /*

         * If the average number of keys per bucket exceeds the fill factor,

         * expand the table.

         */

        hashp->NKEYS++;

        if (do_expand ||

            (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR))

                return (__expand_table(hashp));

        return (0);

}

/*

 *

 * Returns:

 *      pointer on success

 *      NULL on error

 */

extern BUFHEAD *

__add_ovflpage(hashp, bufp)

        HTAB *hashp;

        BUFHEAD *bufp;

{

        __uint16_t *sp;

        __uint16_t ndx, ovfl_num;

#ifdef DEBUG1

        int tmp1, tmp2;

#endif

        sp = (__uint16_t *)bufp->page;

        /* Check if we are dynamically determining the fill factor */

        if (hashp->FFACTOR == DEF_FFACTOR) {

                hashp->FFACTOR = sp[0] >> 1;

                if (hashp->FFACTOR < MIN_FFACTOR)

                        hashp->FFACTOR = MIN_FFACTOR;

        }

        bufp->flags |= BUF_MOD;

        ovfl_num = overflow_page(hashp);

#ifdef DEBUG1

        tmp1 = bufp->addr;

        tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0;

#endif

        if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1)))

                return (NULL);

        bufp->ovfl->flags |= BUF_MOD;

#ifdef DEBUG1

        (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n",

            tmp1, tmp2, bufp->ovfl->addr);

#endif

        ndx = sp[0];

        /*

         * Since a pair is allocated on a page only if there's room to add

         * an overflow page, we know that the OVFL information will fit on

         * the page.

         */

        sp[ndx + 4] = OFFSET(sp);

        sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE;

        sp[ndx + 1] = ovfl_num;

        sp[ndx + 2] = OVFLPAGE;

        sp[0] = ndx + 2;

#ifdef HASH_STATISTICS

        hash_overflows++;

#endif

        return (bufp->ovfl);

}

/*

 * Returns:

 *       0 indicates SUCCESS

 *      -1 indicates FAILURE

 */

extern int

__get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap)

        HTAB *hashp;

        char *p;

        __uint32_t bucket;

        int is_bucket, is_disk, is_bitmap;

{

        int fd, page, size;

        int rsize;

        __uint16_t *bp;

        fd = hashp->fp;

        size = hashp->BSIZE;

        if ((fd == -1) || !is_disk) {

                PAGE_INIT(p);

                return (0);

        }

        if (is_bucket)

                page = BUCKET_TO_PAGE(bucket);

        else

                page = OADDR_TO_PAGE(bucket);

        if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||

            ((rsize = read(fd, p, size)) == -1))

                return (-1);

        bp = (__uint16_t *)p;

        if (!rsize)

                bp[0] = 0;        /* We hit the EOF, so initialize a new page */

        else

                if (rsize != size) {

                        errno = EFTYPE;

                        return (-1);

                }

        if (!is_bitmap && !bp[0]) {

                PAGE_INIT(p);

        } else

               if (hashp->LORDER != DB_BYTE_ORDER) {

                        int i, max;

                        if (is_bitmap) {

                                max = hashp->BSIZE >> 2; /* divide by 4 */

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

                                        M_32_SWAP(((int *)p)[i]);

                        } else {

                                M_16_SWAP(bp[0]);

                                max = bp[0] + 2;

                                for (i = 1; i <= max; i++)

                                        M_16_SWAP(bp[i]);

                        }

                }

        return (0);

}

/*

 * Write page p to disk

 *

 * Returns:

 *       0 ==> OK

 *      -1 ==>failure

 */

extern int

__put_page(hashp, p, bucket, is_bucket, is_bitmap)

        HTAB *hashp;

        char *p;

        __uint32_t bucket;

        int is_bucket, is_bitmap;

{

        int fd, page, size;

        int wsize;

        size = hashp->BSIZE;

        if ((hashp->fp == -1) && open_temp(hashp))

                return (-1);

        fd = hashp->fp;

       if (hashp->LORDER != DB_BYTE_ORDER) {

                int i;

                int max;

                if (is_bitmap) {

                        max = hashp->BSIZE >> 2;        /* divide by 4 */

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

                                M_32_SWAP(((int *)p)[i]);

                } else {

                        max = ((__uint16_t *)p)[0] + 2;

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

                                M_16_SWAP(((__uint16_t *)p)[i]);

                }

        }

        if (is_bucket)

                page = BUCKET_TO_PAGE(bucket);

        else

                page = OADDR_TO_PAGE(bucket);

        if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) ||

            ((wsize = write(fd, p, size)) == -1))

                /* Errno is set */

                return (-1);

        if (wsize != size) {

                errno = EFTYPE;

                return (-1);

        }

        return (0);

}

#define BYTE_MASK       ((1 << INT_BYTE_SHIFT) -1)

/*

 * Initialize a new bitmap page.  Bitmap pages are left in memory

 * once they are read in.

 */