Subversion Repositories openrisc_2011-10-31

/*-

 * 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_bigkey.c       8.3 (Berkeley) 5/31/94";

#endif /* LIBC_SCCS and not lint */

#include <sys/cdefs.h>

/*

 * PACKAGE: hash

 * DESCRIPTION:

 *      Big key/data handling for the hashing package.

 *

 * ROUTINES:

 * External

 *      __big_keydata

 *      __big_split

 *      __big_insert

 *      __big_return

 *      __big_delete

 *      __find_last_page

 * Internal

 *      collect_key

 *      collect_data

 */

#include <sys/param.h>

#include <errno.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#ifdef DEBUG

#include <assert.h>

#endif

#include "db_local.h"

#include "hash.h"

#include "page.h"

#include "extern.h"

static int collect_key(HTAB *, BUFHEAD *, int, DBT *, int);

static int collect_data(HTAB *, BUFHEAD *, int, int);

/*

 * Big_insert

 *

 * You need to do an insert and the key/data pair is too big

 *

 * Returns:

 * 0 ==> OK

 *-1 ==> ERROR

 */

extern int

__big_insert(hashp, bufp, key, val)

        HTAB *hashp;

        BUFHEAD *bufp;

        const DBT *key, *val;

{

        __uint16_t *p;

        int key_size, n, val_size;

        __uint16_t space, move_bytes, off;

        char *cp, *key_data, *val_data;

        cp = bufp->page;                /* Character pointer of p. */

        p = (__uint16_t *)cp;

        key_data = (char *)key->data;

        key_size = key->size;

        val_data = (char *)val->data;

        val_size = val->size;

        /* First move the Key */

        for (space = FREESPACE(p) - BIGOVERHEAD; key_size;

            space = FREESPACE(p) - BIGOVERHEAD) {

                move_bytes = MIN(space, key_size);

                off = OFFSET(p) - move_bytes;

                memmove(cp + off, key_data, move_bytes);

                key_size -= move_bytes;

                key_data += move_bytes;

                n = p[0];

                p[++n] = off;

                p[0] = ++n;

                FREESPACE(p) = off - PAGE_META(n);

                OFFSET(p) = off;

                p[n] = PARTIAL_KEY;

                bufp = __add_ovflpage(hashp, bufp);

                if (!bufp)

                        return (-1);

                n = p[0];

                if (!key_size)

                        if (FREESPACE(p)) {

                                move_bytes = MIN(FREESPACE(p), val_size);

                                off = OFFSET(p) - move_bytes;

                                p[n] = off;

                                memmove(cp + off, val_data, move_bytes);

                                val_data += move_bytes;

                                val_size -= move_bytes;

                                p[n - 2] = FULL_KEY_DATA;

                                FREESPACE(p) = FREESPACE(p) - move_bytes;

                                OFFSET(p) = off;

                        } else

                                p[n - 2] = FULL_KEY;

                p = (__uint16_t *)bufp->page;

                cp = bufp->page;

                bufp->flags |= BUF_MOD;

        }

        /* Now move the data */

        for (space = FREESPACE(p) - BIGOVERHEAD; val_size;

            space = FREESPACE(p) - BIGOVERHEAD) {

                move_bytes = MIN(space, val_size);

                /*

                 * Here's the hack to make sure that if the data ends on the

                 * same page as the key ends, FREESPACE is at least one.

                 */

                if (space == val_size && val_size == val->size)

                        move_bytes--;

                off = OFFSET(p) - move_bytes;

                memmove(cp + off, val_data, move_bytes);

                val_size -= move_bytes;

                val_data += move_bytes;

                n = p[0];

                p[++n] = off;

                p[0] = ++n;

                FREESPACE(p) = off - PAGE_META(n);

                OFFSET(p) = off;

                if (val_size) {

                        p[n] = FULL_KEY;

                        bufp = __add_ovflpage(hashp, bufp);

                        if (!bufp)

                                return (-1);

                        cp = bufp->page;

                        p = (__uint16_t *)cp;

                } else

                        p[n] = FULL_KEY_DATA;

                bufp->flags |= BUF_MOD;

        }

        return (0);

}

/*

 * Called when bufp's page  contains a partial key (index should be 1)

 *

 * All pages in the big key/data pair except bufp are freed.  We cannot

 * free bufp because the page pointing to it is lost and we can't get rid

 * of its pointer.

 *

 * Returns:

 * 0 => OK

 *-1 => ERROR

 */

extern int

__big_delete(hashp, bufp)

        HTAB *hashp;

        BUFHEAD *bufp;

{

        BUFHEAD *last_bfp, *rbufp;

        __uint16_t *bp, pageno;

        int key_done, n;

        rbufp = bufp;

        last_bfp = NULL;

        bp = (__uint16_t *)bufp->page;

        pageno = 0;

        key_done = 0;

        while (!key_done || (bp[2] != FULL_KEY_DATA)) {

                if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA)

                        key_done = 1;

                /*

                 * If there is freespace left on a FULL_KEY_DATA page, then

                 * the data is short and fits entirely on this page, and this

                 * is the last page.

                 */

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

                        break;

                pageno = bp[bp[0] - 1];

                rbufp->flags |= BUF_MOD;

                rbufp = __get_buf(hashp, pageno, rbufp, 0);

                if (last_bfp)

                        __free_ovflpage(hashp, last_bfp);

                last_bfp = rbufp;

                if (!rbufp)

                        return (-1);            /* Error. */

                bp = (__uint16_t *)rbufp->page;

        }

        /*

         * If we get here then rbufp points to the last page of the big

         * key/data pair.  Bufp points to the first one -- it should now be

         * empty pointing to the next page after this pair.  Can't free it

         * because we don't have the page pointing to it.

         */

        /* This is information from the last page of the pair. */

        n = bp[0];

        pageno = bp[n - 1];

        /* Now, bp is the first page of the pair. */

        bp = (__uint16_t *)bufp->page;

        if (n > 2) {

                /* There is an overflow page. */

                bp[1] = pageno;

                bp[2] = OVFLPAGE;

                bufp->ovfl = rbufp->ovfl;

        } else

                /* This is the last page. */

                bufp->ovfl = NULL;

        n -= 2;

        bp[0] = n;

        FREESPACE(bp) = hashp->BSIZE - PAGE_META(n);

        OFFSET(bp) = hashp->BSIZE - 1;

        bufp->flags |= BUF_MOD;

        if (rbufp)

                __free_ovflpage(hashp, rbufp);

        if (last_bfp != rbufp)

                __free_ovflpage(hashp, last_bfp);

        hashp->NKEYS--;

        return (0);

}

/*

 * Returns:

 *  0 = key not found

 * -1 = get next overflow page

 * -2 means key not found and this is big key/data

 * -3 error

 */

extern int

__find_bigpair(hashp, bufp, ndx, key, size)

        HTAB *hashp;

        BUFHEAD *bufp;

        int ndx;

        char *key;

        int size;

{

        __uint16_t *bp;

        char *p;

        int ksize;

        __uint16_t bytes;

        char *kkey;

        bp = (__uint16_t *)bufp->page;

        p = bufp->page;

        ksize = size;

        kkey = key;

        for (bytes = hashp->BSIZE - bp[ndx];

            bytes <= size && bp[ndx + 1] == PARTIAL_KEY;

            bytes = hashp->BSIZE - bp[ndx]) {

                if (memcmp(p + bp[ndx], kkey, bytes))

                        return (-2);

                kkey += bytes;

                ksize -= bytes;

                bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);

                if (!bufp)

                        return (-3);

                p = bufp->page;

                bp = (__uint16_t *)p;

                ndx = 1;

        }

        if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {

#ifdef HASH_STATISTICS

                ++hash_collisions;

#endif

                return (-2);

        } else

                return (ndx);

}

/*

 * Given the buffer pointer of the first overflow page of a big pair,

 * find the end of the big pair

 *

 * This will set bpp to the buffer header of the last page of the big pair.

 * It will return the pageno of the overflow page following the last page

 * of the pair; 0 if there isn't any (i.e. big pair is the last key in the

 * bucket)

 */

extern __uint16_t

__find_last_page(hashp, bpp)

        HTAB *hashp;

        BUFHEAD **bpp;

{

        BUFHEAD *bufp;

        __uint16_t *bp, pageno;

        int n;

        bufp = *bpp;

        bp = (__uint16_t *)bufp->page;

        for (;;) {

                n = bp[0];

                /*

                 * This is the last page if: the tag is FULL_KEY_DATA and

                 * either only 2 entries OVFLPAGE marker is explicit there

                 * is freespace on the page.

                 */

                if (bp[2] == FULL_KEY_DATA &&

                    ((n == 2) || (bp[n] == OVFLPAGE) || (FREESPACE(bp))))

                        break;

                pageno = bp[n - 1];

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

                if (!bufp)

                        return (0);      /* Need to indicate an error! */

                bp = (__uint16_t *)bufp->page;

        }

        *bpp = bufp;

        if (bp[0] > 2)

                return (bp[3]);

        else

                return (0);

}

/*

 * Return the data for the key/data pair that begins on this page at this

 * index (index should always be 1).

 */

extern int

__big_return(hashp, bufp, ndx, val, set_current)

        HTAB *hashp;

        BUFHEAD *bufp;

        int ndx;

        DBT *val;

        int set_current;

{

        BUFHEAD *save_p;

        __uint16_t *bp, len, off, save_addr;

        char *tp;

        bp = (__uint16_t *)bufp->page;

        while (bp[ndx + 1] == PARTIAL_KEY) {

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

                if (!bufp)

                        return (-1);

                bp = (__uint16_t *)bufp->page;

                ndx = 1;

        }

        if (bp[ndx + 1] == FULL_KEY) {

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

                if (!bufp)

                        return (-1);

                bp = (__uint16_t *)bufp->page;

                save_p = bufp;

                save_addr = save_p->addr;

                off = bp[1];

                len = 0;

        } else

                if (!FREESPACE(bp)) {

                        /*

                         * This is a hack.  We can't distinguish between

                         * FULL_KEY_DATA that contains complete data or

                         * incomplete data, so we require that if the data

                         * is complete, there is at least 1 byte of free

                         * space left.

                         */

                        off = bp[bp[0]];

                        len = bp[1] - off;

                        save_p = bufp;

                        save_addr = bufp->addr;

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

                        if (!bufp)

                                return (-1);

                        bp = (__uint16_t *)bufp->page;

                } else {

                        /* The data is all on one page. */

                        tp = (char *)bp;

                        off = bp[bp[0]];

                        val->data = (u_char *)tp + off;

                        val->size = bp[1] - off;

                        if (set_current) {

                                if (bp[0] == 2) {        /* No more buckets in

                                                         * chain */

                                        hashp->cpage = NULL;

                                        hashp->cbucket++;

                                        hashp->cndx = 1;

                                } else {

                                        hashp->cpage = __get_buf(hashp,

                                            bp[bp[0] - 1], bufp, 0);

                                        if (!hashp->cpage)

                                                return (-1);

                                        hashp->cndx = 1;

                                        if (!((__uint16_t *)

                                            hashp->cpage->page)[0]) {

                                                hashp->cbucket++;

                                                hashp->cpage = NULL;

                                        }

                                }

                        }

                        return (0);

                }

        val->size = collect_data(hashp, bufp, (int)len, set_current);

        if (val->size == -1)

                return (-1);

        if (save_p->addr != save_addr) {

                /* We are pretty short on buffers. */

                errno = EINVAL;                 /* OUT OF BUFFERS */

                return (-1);

        }

        memmove(hashp->tmp_buf, (save_p->page) + off, len);

        val->data = (u_char *)hashp->tmp_buf;

        return (0);

}

/*

 * Count how big the total datasize is by recursing through the pages.  Then

 * allocate a buffer and copy the data as you recurse up.

 */

static int

collect_data(hashp, bufp, len, set)

        HTAB *hashp;

        BUFHEAD *bufp;

        int len, set;

{

        __uint16_t *bp;

        char *p;

        BUFHEAD *xbp;

        __uint16_t save_addr;

        int mylen, totlen;

        p = bufp->page;

        bp = (__uint16_t *)p;

        mylen = hashp->BSIZE - bp[1];

        save_addr = bufp->addr;

        if (bp[2] == FULL_KEY_DATA) {           /* End of Data */

                totlen = len + mylen;

                if (hashp->tmp_buf)

                        free(hashp->tmp_buf);

                if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)

                        return (-1);

                if (set) {

                        hashp->cndx = 1;

                        if (bp[0] == 2) {        /* No more buckets in chain */

                                hashp->cpage = NULL;

                                hashp->cbucket++;

                        } else {

                                hashp->cpage =

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

                                if (!hashp->cpage)

                                        return (-1);

                                else if (!((__uint16_t *)hashp->cpage->page)[0]) {

                                        hashp->cbucket++;

                                        hashp->cpage = NULL;

                                }

                        }

                }

        } else {

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

                if (!xbp || ((totlen =

                    collect_data(hashp, xbp, len + mylen, set)) < 1))

                        return (-1);

        }

        if (bufp->addr != save_addr) {

                errno = EINVAL;                 /* Out of buffers. */

                return (-1);

        }

        memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);

        return (totlen);

}

/*

 * Fill in the key and data for this big pair.

 */

extern int

__big_keydata(hashp, bufp, key, val, set)

        HTAB *hashp;

        BUFHEAD *bufp;

        DBT *key, *val;

        int set;

{

        key->size = collect_key(hashp, bufp, 0, val, set);

        if (key->size == -1)

                return (-1);

        key->data = (u_char *)hashp->tmp_key;

        return (0);

}

/*

 * Count how big the total key size is by recursing through the pages.  Then

 * collect the data, allocate a buffer and copy the key as you recurse up.

 */

static int

collect_key(hashp, bufp, len, val, set)

        HTAB *hashp;

        BUFHEAD *bufp;

        int len;

        DBT *val;

        int set;

{

        BUFHEAD *xbp;

        char *p;

        int mylen, totlen;

        __uint16_t *bp, save_addr;

        p = bufp->page;

        bp = (__uint16_t *)p;

        mylen = hashp->BSIZE - bp[1];

        save_addr = bufp->addr;

        totlen = len + mylen;

        if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */

                if (hashp->tmp_key != NULL)

                        free(hashp->tmp_key);

                if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)

                        return (-1);

                if (__big_return(hashp, bufp, 1, val, set))

                        return (-1);

        } else {

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

                if (!xbp || ((totlen =

                    collect_key(hashp, xbp, totlen, val, set)) < 1))

                        return (-1);

        }

        if (bufp->addr != save_addr) {

                errno = EINVAL;         /* MIS -- OUT OF BUFFERS */

                return (-1);

        }

        memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);

        return (totlen);

}

/*

 * Returns:

 *  0 => OK

 * -1 => error

 */

extern int

__big_split(hashp, op, np, big_keyp, addr, obucket, ret)

        HTAB *hashp;

        BUFHEAD *op;    /* Pointer to where to put keys that go in old bucket */

        BUFHEAD *np;    /* Pointer to new bucket page */

                        /* Pointer to first page containing the big key/data */

        BUFHEAD *big_keyp;

        int addr;       /* Address of big_keyp */

        __uint32_t   obucket;/* Old Bucket */

        SPLIT_RETURN *ret;

{

        BUFHEAD *tmpp;

        __uint16_t *tp;

        BUFHEAD *bp;

        DBT key, val;

        __uint32_t change;

        __uint16_t free_space, n, off;

        bp = big_keyp;

        /* Now figure out where the big key/data goes */

        if (__big_keydata(hashp, big_keyp, &key, &val, 0))

                return (-1);

        change = (__call_hash(hashp, key.data, key.size) != obucket);

        if ( (ret->next_addr = __find_last_page(hashp, &big_keyp)) ) {

                if (!(ret->nextp =

                    __get_buf(hashp, ret->next_addr, big_keyp, 0)))

                        return (-1);;

        } else

                ret->nextp = NULL;

        /* Now make one of np/op point to the big key/data pair */

#ifdef DEBUG

        assert(np->ovfl == NULL);

#endif

        if (change)

                tmpp = np;

        else

                tmpp = op;

        tmpp->flags |= BUF_MOD;

#ifdef DEBUG1

        (void)fprintf(stderr,

            "BIG_SPLIT: %d->ovfl was %d is now %d\n", tmpp->addr,

            (tmpp->ovfl ? tmpp->ovfl->addr : 0), (bp ? bp->addr : 0));

#endif

        tmpp->ovfl = bp;        /* one of op/np point to big_keyp */

        tp = (__uint16_t *)tmpp->page;

#ifdef DEBUG

        assert(FREESPACE(tp) >= OVFLSIZE);

#endif

        n = tp[0];

        off = OFFSET(tp);

        free_space = FREESPACE(tp);

        tp[++n] = (__uint16_t)addr;

        tp[++n] = OVFLPAGE;

        tp[0] = n;

        OFFSET(tp) = off;

        FREESPACE(tp) = free_space - OVFLSIZE;

        /*

         * Finally, set the new and old return values. BIG_KEYP contains a

         * pointer to the last page of the big key_data pair. Make sure that

         * big_keyp has no following page (2 elements) or create an empty

         * following page.

         */

        ret->newp = np;

        ret->oldp = op;

        tp = (__uint16_t *)big_keyp->page;

        big_keyp->flags |= BUF_MOD;

        if (tp[0] > 2) {

                /*

                 * There may be either one or two offsets on this page.  If

                 * there is one, then the overflow page is linked on normally

                 * and tp[4] is OVFLPAGE.  If there are two, tp[4] contains

                 * the second offset and needs to get stuffed in after the

                 * next overflow page is added.

                 */

                n = tp[4];

                free_space = FREESPACE(tp);

                off = OFFSET(tp);