BSD 4_4_Lite1 release
[unix-history] / usr / src / lib / libc / db / hash / hash_bigkey.c
index beddf00..b747fbc 100644 (file)
@@ -1,15 +1,41 @@
 /*-
 /*-
- * Copyright (c) 1990 The Regents of the University of California.
- * All rights reserved.
+ * Copyright (c) 1990, 1993
+ *     The Regents of the University of California.  All rights reserved.
  *
  * This code is derived from software contributed to Berkeley by
  * Margo Seltzer.
  *
  *
  * This code is derived from software contributed to Berkeley by
  * Margo Seltzer.
  *
- * %sccs.include.redist.c%
+ * 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.
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)
-static char sccsid[] = "@(#)hash_bigkey.c      5.6 (Berkeley) %G%";
+static char sccsid[] = "@(#)hash_bigkey.c      8.2 (Berkeley) 2/21/94";
 #endif /* LIBC_SCCS and not lint */
 
 /*
 #endif /* LIBC_SCCS and not lint */
 
 /*
@@ -31,20 +57,23 @@ static char sccsid[] = "@(#)hash_bigkey.c   5.6 (Berkeley) %G%";
  */
 
 #include <sys/param.h>
  */
 
 #include <sys/param.h>
+
 #include <errno.h>
 #include <errno.h>
-#include <db.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+
 #ifdef DEBUG
 #include <assert.h>
 #endif
 #ifdef DEBUG
 #include <assert.h>
 #endif
+
+#include <db.h>
 #include "hash.h"
 #include "page.h"
 #include "extern.h"
 
 #include "hash.h"
 #include "page.h"
 #include "extern.h"
 
-static int collect_key __P((BUFHEAD *, int, DBT *, int));
-static int collect_data __P((BUFHEAD *, int, int));
+static int collect_key __P((HTAB *, BUFHEAD *, int, DBT *, int));
+static int collect_data __P((HTAB *, BUFHEAD *, int, int));
 
 /*
  * Big_insert
 
 /*
  * Big_insert
@@ -56,7 +85,8 @@ static int collect_data __P((BUFHEAD *, int, int));
  *-1 ==> ERROR
  */
 extern int
  *-1 ==> ERROR
  */
 extern int
-__big_insert(bufp, key, val)
+__big_insert(hashp, bufp, key, val)
+       HTAB *hashp;
        BUFHEAD *bufp;
        const DBT *key, *val;
 {
        BUFHEAD *bufp;
        const DBT *key, *val;
 {
@@ -78,7 +108,7 @@ __big_insert(bufp, key, val)
            space = FREESPACE(p) - BIGOVERHEAD) {
                move_bytes = MIN(space, key_size);
                off = OFFSET(p) - move_bytes;
            space = FREESPACE(p) - BIGOVERHEAD) {
                move_bytes = MIN(space, key_size);
                off = OFFSET(p) - move_bytes;
-               bcopy(key_data, cp + off, move_bytes);
+               memmove(cp + off, key_data, move_bytes);
                key_size -= move_bytes;
                key_data += move_bytes;
                n = p[0];
                key_size -= move_bytes;
                key_data += move_bytes;
                n = p[0];
@@ -87,7 +117,7 @@ __big_insert(bufp, key, val)
                FREESPACE(p) = off - PAGE_META(n);
                OFFSET(p) = off;
                p[n] = PARTIAL_KEY;
                FREESPACE(p) = off - PAGE_META(n);
                OFFSET(p) = off;
                p[n] = PARTIAL_KEY;
-               bufp = __add_ovflpage(bufp);
+               bufp = __add_ovflpage(hashp, bufp);
                if (!bufp)
                        return (-1);
                n = p[0];
                if (!bufp)
                        return (-1);
                n = p[0];
@@ -96,7 +126,7 @@ __big_insert(bufp, key, val)
                                move_bytes = MIN(FREESPACE(p), val_size);
                                off = OFFSET(p) - move_bytes;
                                p[n] = off;
                                move_bytes = MIN(FREESPACE(p), val_size);
                                off = OFFSET(p) - move_bytes;
                                p[n] = off;
-                               bcopy(val_data, cp + off, move_bytes);
+                               memmove(cp + off, val_data, move_bytes);
                                val_data += move_bytes;
                                val_size -= move_bytes;
                                p[n - 2] = FULL_KEY_DATA;
                                val_data += move_bytes;
                                val_size -= move_bytes;
                                p[n - 2] = FULL_KEY_DATA;
@@ -120,7 +150,7 @@ __big_insert(bufp, key, val)
                if (space == val_size && val_size == val->size)
                        move_bytes--;
                off = OFFSET(p) - move_bytes;
                if (space == val_size && val_size == val->size)
                        move_bytes--;
                off = OFFSET(p) - move_bytes;
-               bcopy(val_data, cp + off, move_bytes);
+               memmove(cp + off, val_data, move_bytes);
                val_size -= move_bytes;
                val_data += move_bytes;
                n = p[0];
                val_size -= move_bytes;
                val_data += move_bytes;
                n = p[0];
@@ -130,7 +160,7 @@ __big_insert(bufp, key, val)
                OFFSET(p) = off;
                if (val_size) {
                        p[n] = FULL_KEY;
                OFFSET(p) = off;
                if (val_size) {
                        p[n] = FULL_KEY;
-                       bufp = __add_ovflpage(bufp);
+                       bufp = __add_ovflpage(hashp, bufp);
                        if (!bufp)
                                return (-1);
                        cp = bufp->page;
                        if (!bufp)
                                return (-1);
                        cp = bufp->page;
@@ -154,9 +184,9 @@ __big_insert(bufp, key, val)
  *-1 => ERROR
  */
 extern int
  *-1 => ERROR
  */
 extern int
-__big_delete(bufp, ndx)
+__big_delete(hashp, bufp)
+       HTAB *hashp;
        BUFHEAD *bufp;
        BUFHEAD *bufp;
-       int ndx;
 {
        register BUFHEAD *last_bfp, *rbufp;
        u_short *bp, pageno;
 {
        register BUFHEAD *last_bfp, *rbufp;
        u_short *bp, pageno;
@@ -181,9 +211,9 @@ __big_delete(bufp, ndx)
                        break;
                pageno = bp[bp[0] - 1];
                rbufp->flags |= BUF_MOD;
                        break;
                pageno = bp[bp[0] - 1];
                rbufp->flags |= BUF_MOD;
-               rbufp = __get_buf(pageno, rbufp, 0);
+               rbufp = __get_buf(hashp, pageno, rbufp, 0);
                if (last_bfp)
                if (last_bfp)
-                       __free_ovflpage(last_bfp);
+                       __free_ovflpage(hashp, last_bfp);
                last_bfp = rbufp;
                if (!rbufp)
                        return (-1);            /* Error. */
                last_bfp = rbufp;
                if (!rbufp)
                        return (-1);            /* Error. */
@@ -218,9 +248,9 @@ __big_delete(bufp, ndx)
 
        bufp->flags |= BUF_MOD;
        if (rbufp)
 
        bufp->flags |= BUF_MOD;
        if (rbufp)
-               __free_ovflpage(rbufp);
+               __free_ovflpage(hashp, rbufp);
        if (last_bfp != rbufp)
        if (last_bfp != rbufp)
-               __free_ovflpage(last_bfp);
+               __free_ovflpage(hashp, last_bfp);
 
        hashp->NKEYS--;
        return (0);
 
        hashp->NKEYS--;
        return (0);
@@ -233,7 +263,8 @@ __big_delete(bufp, ndx)
  * -3 error
  */
 extern int
  * -3 error
  */
 extern int
-__find_bigpair(bufp, ndx, key, size)
+__find_bigpair(hashp, bufp, ndx, key, size)
+       HTAB *hashp;
        BUFHEAD *bufp;
        int ndx;
        char *key;
        BUFHEAD *bufp;
        int ndx;
        char *key;
@@ -253,11 +284,11 @@ __find_bigpair(bufp, ndx, key, size)
        for (bytes = hashp->BSIZE - bp[ndx];
            bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
            bytes = hashp->BSIZE - bp[ndx]) {
        for (bytes = hashp->BSIZE - bp[ndx];
            bytes <= size && bp[ndx + 1] == PARTIAL_KEY;
            bytes = hashp->BSIZE - bp[ndx]) {
-               if (bcmp(p + bp[ndx], kkey, bytes))
+               if (memcmp(p + bp[ndx], kkey, bytes))
                        return (-2);
                kkey += bytes;
                ksize -= bytes;
                        return (-2);
                kkey += bytes;
                ksize -= bytes;
-               bufp = __get_buf(bp[ndx + 2], bufp, 0);
+               bufp = __get_buf(hashp, bp[ndx + 2], bufp, 0);
                if (!bufp)
                        return (-3);
                p = bufp->page;
                if (!bufp)
                        return (-3);
                p = bufp->page;
@@ -265,7 +296,7 @@ __find_bigpair(bufp, ndx, key, size)
                ndx = 1;
        }
 
                ndx = 1;
        }
 
-       if (bytes != ksize || bcmp(p + bp[ndx], kkey, bytes)) {
+       if (bytes != ksize || memcmp(p + bp[ndx], kkey, bytes)) {
 #ifdef HASH_STATISTICS
                ++hash_collisions;
 #endif
 #ifdef HASH_STATISTICS
                ++hash_collisions;
 #endif
@@ -284,7 +315,8 @@ __find_bigpair(bufp, ndx, key, size)
  * bucket)
  */
 extern u_short
  * bucket)
  */
 extern u_short
-__find_last_page(bpp)
+__find_last_page(hashp, bpp)
+       HTAB *hashp;
        BUFHEAD **bpp;
 {
        BUFHEAD *bufp;
        BUFHEAD **bpp;
 {
        BUFHEAD *bufp;
@@ -306,7 +338,7 @@ __find_last_page(bpp)
                        break;
 
                pageno = bp[n - 1];
                        break;
 
                pageno = bp[n - 1];
-               bufp = __get_buf(pageno, bufp, 0);
+               bufp = __get_buf(hashp, pageno, bufp, 0);
                if (!bufp)
                        return (0);     /* Need to indicate an error! */
                bp = (u_short *)bufp->page;
                if (!bufp)
                        return (0);     /* Need to indicate an error! */
                bp = (u_short *)bufp->page;
@@ -324,7 +356,8 @@ __find_last_page(bpp)
  * index (index should always be 1).
  */
 extern int
  * index (index should always be 1).
  */
 extern int
-__big_return(bufp, ndx, val, set_current)
+__big_return(hashp, bufp, ndx, val, set_current)
+       HTAB *hashp;
        BUFHEAD *bufp;
        int ndx;
        DBT *val;
        BUFHEAD *bufp;
        int ndx;
        DBT *val;
@@ -336,7 +369,7 @@ __big_return(bufp, ndx, val, set_current)
 
        bp = (u_short *)bufp->page;
        while (bp[ndx + 1] == PARTIAL_KEY) {
 
        bp = (u_short *)bufp->page;
        while (bp[ndx + 1] == PARTIAL_KEY) {
-               bufp = __get_buf(bp[bp[0] - 1], bufp, 0);
+               bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
                if (!bufp)
                        return (-1);
                bp = (u_short *)bufp->page;
                if (!bufp)
                        return (-1);
                bp = (u_short *)bufp->page;
@@ -344,7 +377,7 @@ __big_return(bufp, ndx, val, set_current)
        }
 
        if (bp[ndx + 1] == FULL_KEY) {
        }
 
        if (bp[ndx + 1] == FULL_KEY) {
-               bufp = __get_buf(bp[bp[0] - 1], bufp, 0);
+               bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
                if (!bufp)
                        return (-1);
                bp = (u_short *)bufp->page;
                if (!bufp)
                        return (-1);
                bp = (u_short *)bufp->page;
@@ -365,7 +398,7 @@ __big_return(bufp, ndx, val, set_current)
                        len = bp[1] - off;
                        save_p = bufp;
                        save_addr = bufp->addr;
                        len = bp[1] - off;
                        save_p = bufp;
                        save_addr = bufp->addr;
-                       bufp = __get_buf(bp[bp[0] - 1], bufp, 0);
+                       bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
                        if (!bufp)
                                return (-1);
                        bp = (u_short *)bufp->page;
                        if (!bufp)
                                return (-1);
                        bp = (u_short *)bufp->page;
@@ -382,8 +415,8 @@ __big_return(bufp, ndx, val, set_current)
                                        hashp->cbucket++;
                                        hashp->cndx = 1;
                                } else {
                                        hashp->cbucket++;
                                        hashp->cndx = 1;
                                } else {
-                                       hashp->cpage =
-                                           __get_buf(bp[bp[0] - 1], bufp, 0);
+                                       hashp->cpage = __get_buf(hashp,
+                                           bp[bp[0] - 1], bufp, 0);
                                        if (!hashp->cpage)
                                                return (-1);
                                        hashp->cndx = 1;
                                        if (!hashp->cpage)
                                                return (-1);
                                        hashp->cndx = 1;
@@ -397,7 +430,7 @@ __big_return(bufp, ndx, val, set_current)
                        return (0);
                }
 
                        return (0);
                }
 
-       val->size = collect_data(bufp, len, set_current);
+       val->size = collect_data(hashp, bufp, (int)len, set_current);
        if (val->size == -1)
                return (-1);
        if (save_p->addr != save_addr) {
        if (val->size == -1)
                return (-1);
        if (save_p->addr != save_addr) {
@@ -405,7 +438,7 @@ __big_return(bufp, ndx, val, set_current)
                errno = EINVAL;                 /* OUT OF BUFFERS */
                return (-1);
        }
                errno = EINVAL;                 /* OUT OF BUFFERS */
                return (-1);
        }
-       bcopy((save_p->page) + off, hashp->tmp_buf, len);
+       memmove(hashp->tmp_buf, (save_p->page) + off, len);
        val->data = (u_char *)hashp->tmp_buf;
        return (0);
 }
        val->data = (u_char *)hashp->tmp_buf;
        return (0);
 }
@@ -414,7 +447,8 @@ __big_return(bufp, ndx, val, set_current)
  * allocate a buffer and copy the data as you recurse up.
  */
 static int
  * allocate a buffer and copy the data as you recurse up.
  */
 static int
-collect_data(bufp, len, set)
+collect_data(hashp, bufp, len, set)
+       HTAB *hashp;
        BUFHEAD *bufp;
        int len, set;
 {
        BUFHEAD *bufp;
        int len, set;
 {
@@ -433,8 +467,7 @@ collect_data(bufp, len, set)
                totlen = len + mylen;
                if (hashp->tmp_buf)
                        free(hashp->tmp_buf);
                totlen = len + mylen;
                if (hashp->tmp_buf)
                        free(hashp->tmp_buf);
-               hashp->tmp_buf = malloc(totlen);
-               if (!hashp->tmp_buf)
+               if ((hashp->tmp_buf = (char *)malloc(totlen)) == NULL)
                        return (-1);
                if (set) {
                        hashp->cndx = 1;
                        return (-1);
                if (set) {
                        hashp->cndx = 1;
@@ -443,7 +476,7 @@ collect_data(bufp, len, set)
                                hashp->cbucket++;
                        } else {
                                hashp->cpage =
                                hashp->cbucket++;
                        } else {
                                hashp->cpage =
-                                   __get_buf(bp[bp[0] - 1], bufp, 0);
+                                   __get_buf(hashp, bp[bp[0] - 1], bufp, 0);
                                if (!hashp->cpage)
                                        return (-1);
                                else if (!((u_short *)hashp->cpage->page)[0]) {
                                if (!hashp->cpage)
                                        return (-1);
                                else if (!((u_short *)hashp->cpage->page)[0]) {
@@ -453,16 +486,16 @@ collect_data(bufp, len, set)
                        }
                }
        } else {
                        }
                }
        } else {
-               xbp = __get_buf(bp[bp[0] - 1], bufp, 0);
-               if (!xbp ||
-                   ((totlen = collect_data(xbp, len + mylen, set)) < 1))
+               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);
        }
                        return (-1);
        }
        if (bufp->addr != save_addr) {
                errno = EINVAL;                 /* Out of buffers. */
                return (-1);
        }
-       bcopy((bufp->page) + bp[1], &hashp->tmp_buf[len], mylen);
+       memmove(&hashp->tmp_buf[len], (bufp->page) + bp[1], mylen);
        return (totlen);
 }
 
        return (totlen);
 }
 
@@ -470,13 +503,13 @@ collect_data(bufp, len, set)
  * Fill in the key and data for this big pair.
  */
 extern int
  * Fill in the key and data for this big pair.
  */
 extern int
-__big_keydata(bufp, ndx, key, val, set)
+__big_keydata(hashp, bufp, key, val, set)
+       HTAB *hashp;
        BUFHEAD *bufp;
        BUFHEAD *bufp;
-       int ndx;
        DBT *key, *val;
        int set;
 {
        DBT *key, *val;
        int set;
 {
-       key->size = collect_key(bufp, 0, val, set);
+       key->size = collect_key(hashp, bufp, 0, val, set);
        if (key->size == -1)
                return (-1);
        key->data = (u_char *)hashp->tmp_key;
        if (key->size == -1)
                return (-1);
        key->data = (u_char *)hashp->tmp_key;
@@ -488,7 +521,8 @@ __big_keydata(bufp, ndx, key, val, set)
  * collect the data, allocate a buffer and copy the key as you recurse up.
  */
 static int
  * collect the data, allocate a buffer and copy the key as you recurse up.
  */
 static int
-collect_key(bufp, len, val, set)
+collect_key(hashp, bufp, len, val, set)
+       HTAB *hashp;
        BUFHEAD *bufp;
        int len;
        DBT *val;
        BUFHEAD *bufp;
        int len;
        DBT *val;
@@ -506,23 +540,23 @@ collect_key(bufp, len, val, set)
        save_addr = bufp->addr;
        totlen = len + mylen;
        if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
        save_addr = bufp->addr;
        totlen = len + mylen;
        if (bp[2] == FULL_KEY || bp[2] == FULL_KEY_DATA) {    /* End of Key. */
-               if (hashp->tmp_key)
+               if (hashp->tmp_key != NULL)
                        free(hashp->tmp_key);
                        free(hashp->tmp_key);
-               hashp->tmp_key = malloc(totlen);
-               if (!hashp->tmp_key)
+               if ((hashp->tmp_key = (char *)malloc(totlen)) == NULL)
+                       return (-1);
+               if (__big_return(hashp, bufp, 1, val, set))
                        return (-1);
                        return (-1);
-               __big_return(bufp, 1, val, set);
        } else {
        } else {
-               xbp = __get_buf(bp[bp[0] - 1], bufp, 0);
-               if (!xbp ||
-                   ((totlen = collect_key(xbp, totlen, val, set)) < 1))
+               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);
        }
                        return (-1);
        }
        if (bufp->addr != save_addr) {
                errno = EINVAL;         /* MIS -- OUT OF BUFFERS */
                return (-1);
        }
-       bcopy((bufp->page) + bp[1], &hashp->tmp_key[len], mylen);
+       memmove(&hashp->tmp_key[len], (bufp->page) + bp[1], mylen);
        return (totlen);
 }
 
        return (totlen);
 }
 
@@ -532,7 +566,8 @@ collect_key(bufp, len, val, set)
  * -1 => error
  */
 extern int
  * -1 => error
  */
 extern int
-__big_split(op, np, big_keyp, addr, obucket, ret)
+__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 *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 */
@@ -551,12 +586,13 @@ __big_split(op, np, big_keyp, addr, obucket, ret)
        bp = big_keyp;
 
        /* Now figure out where the big key/data goes */
        bp = big_keyp;
 
        /* Now figure out where the big key/data goes */
-       if (__big_keydata(big_keyp, 1, &key, &val, 0))
+       if (__big_keydata(hashp, big_keyp, &key, &val, 0))
                return (-1);
                return (-1);
-       change = (__call_hash(key.data, key.size) != obucket);
+       change = (__call_hash(hashp, key.data, key.size) != obucket);
 
 
-       if (ret->next_addr = __find_last_page(&big_keyp)) {
-               if (!(ret->nextp = __get_buf(ret->next_addr, big_keyp, 0)))
+       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;
                        return (-1);;
        } else
                ret->nextp = NULL;
@@ -616,7 +652,7 @@ __big_split(op, np, big_keyp, addr, obucket, ret)
                tp[0] -= 2;
                FREESPACE(tp) = free_space + OVFLSIZE;
                OFFSET(tp) = off;
                tp[0] -= 2;
                FREESPACE(tp) = free_space + OVFLSIZE;
                OFFSET(tp) = off;
-               tmpp = __add_ovflpage(big_keyp);
+               tmpp = __add_ovflpage(hashp, big_keyp);
                if (!tmpp)
                        return (-1);
                tp[4] = n;
                if (!tmpp)
                        return (-1);
                tp[4] = n;