diff options
Diffstat (limited to 'src/util/db2/hash')
| -rw-r--r-- | src/util/db2/hash/Makefile.inc | 6 | ||||
| -rw-r--r-- | src/util/db2/hash/dbm.c | 297 | ||||
| -rw-r--r-- | src/util/db2/hash/extern.h | 76 | ||||
| -rw-r--r-- | src/util/db2/hash/hash.c | 1068 | ||||
| -rw-r--r-- | src/util/db2/hash/hash.c.patch | 109 | ||||
| -rw-r--r-- | src/util/db2/hash/hash.h | 196 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_bigkey.c | 483 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_debug.c | 106 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_func.c | 196 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_log2.c | 52 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_page.c | 1380 | ||||
| -rw-r--r-- | src/util/db2/hash/hsearch.c | 107 | ||||
| -rw-r--r-- | src/util/db2/hash/page.h | 178 | ||||
| -rw-r--r-- | src/util/db2/hash/page.h.patch | 42 | ||||
| -rw-r--r-- | src/util/db2/hash/search.h | 51 |
15 files changed, 4347 insertions, 0 deletions
diff --git a/src/util/db2/hash/Makefile.inc b/src/util/db2/hash/Makefile.inc new file mode 100644 index 000000000..87746f721 --- /dev/null +++ b/src/util/db2/hash/Makefile.inc @@ -0,0 +1,6 @@ +# @(#)Makefile.inc 8.2 (Berkeley) 11/7/95 + +.PATH: ${.CURDIR}/db/hash + +SRCS+= hash.c hash_bigkey.c hash_buf.c hash_func.c hash_log2.c \ + hash_page.c hsearch.c dbm.c diff --git a/src/util/db2/hash/dbm.c b/src/util/db2/hash/dbm.c new file mode 100644 index 000000000..a5a31f45b --- /dev/null +++ b/src/util/db2/hash/dbm.c @@ -0,0 +1,297 @@ +/*- + * 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. + * + * 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) +static char sccsid[] = "@(#)dbm.c 8.6 (Berkeley) 11/7/95"; +#endif /* LIBC_SCCS and not lint */ + +#include "db-int.h" + +#include <sys/param.h> + +#include <fcntl.h> +#include <stdio.h> +#include <string.h> + +#include "db-ndbm.h" +#include "hash.h" + +/* + * + * This package provides dbm and ndbm compatible interfaces to DB. + * First are the DBM routines, which call the NDBM routines, and + * the NDBM routines, which call the DB routines. + */ +static DBM *__cur_db; + +static void no_open_db __P((void)); + +int +dbminit(file) + char *file; +{ + if (__cur_db != NULL) + (void)dbm_close(__cur_db); + if ((__cur_db = dbm_open(file, O_RDWR, 0)) != NULL) + return (0); + if ((__cur_db = dbm_open(file, O_RDONLY, 0)) != NULL) + return (0); + return (-1); +} + +datum +fetch(key) + datum key; +{ + datum item; + + if (__cur_db == NULL) { + no_open_db(); + item.dptr = 0; + return (item); + } + return (dbm_fetch(__cur_db, key)); +} + +datum +firstkey() +{ + datum item; + + if (__cur_db == NULL) { + no_open_db(); + item.dptr = 0; + return (item); + } + return (dbm_firstkey(__cur_db)); +} + +datum +nextkey(key) + datum key; +{ + datum item; + + if (__cur_db == NULL) { + no_open_db(); + item.dptr = 0; + return (item); + } + return (dbm_nextkey(__cur_db)); +} + +int +delete(key) + datum key; +{ + if (__cur_db == NULL) { + no_open_db(); + return (-1); + } + return (dbm_delete(__cur_db, key)); +} + +int +store(key, dat) + datum key, dat; +{ + if (__cur_db == NULL) { + no_open_db(); + return (-1); + } + return (dbm_store(__cur_db, key, dat, DBM_REPLACE)); +} + +static void +no_open_db() +{ + (void)fprintf(stderr, "dbm: no open database.\n"); +} + +/* + * Returns: + * *DBM on success + * NULL on failure + */ +DBM * +dbm_open(file, flags, mode) + const char *file; + int flags, mode; +{ + HASHINFO info; + char path[MAXPATHLEN]; + + info.bsize = 4096; + info.ffactor = 40; + info.nelem = 1; + info.cachesize = 0; + info.hash = NULL; + info.lorder = 0; + (void)strcpy(path, file); + (void)strcat(path, DBM_SUFFIX); + return ((DBM *)__hash_open(path, flags, mode, &info, 0)); +} + +/* + * Returns: + * Nothing. + */ +void +dbm_close(db) + DBM *db; +{ + (void)(db->close)(db); +} + +/* + * Returns: + * DATUM on success + * NULL on failure + */ +datum +dbm_fetch(db, key) + DBM *db; + datum key; +{ + datum retval; + int status; + + status = (db->get)(db, (DBT *)&key, (DBT *)&retval, 0); + if (status) { + retval.dptr = NULL; + retval.dsize = 0; + } + return (retval); +} + +/* + * Returns: + * DATUM on success + * NULL on failure + */ +datum +dbm_firstkey(db) + DBM *db; +{ + int status; + datum retdata, retkey; + + status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST); + if (status) + retkey.dptr = NULL; + return (retkey); +} + +/* + * Returns: + * DATUM on success + * NULL on failure + */ +datum +dbm_nextkey(db) + DBM *db; +{ + int status; + datum retdata, retkey; + + status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT); + if (status) + retkey.dptr = NULL; + return (retkey); +} + +/* + * Returns: + * 0 on success + * <0 failure + */ +int +dbm_delete(db, key) + DBM *db; + datum key; +{ + int status; + + status = (db->del)(db, (DBT *)&key, 0); + if (status) + return (-1); + else + return (0); +} + +/* + * Returns: + * 0 on success + * <0 failure + * 1 if DBM_INSERT and entry exists + */ +int +dbm_store(db, key, content, flags) + DBM *db; + datum key, content; + int flags; +{ + return ((db->put)(db, (DBT *)&key, (DBT *)&content, + (flags == DBM_INSERT) ? R_NOOVERWRITE : 0)); +} + +int +dbm_error(db) + DBM *db; +{ + HTAB *hp; + + hp = (HTAB *)db->internal; + return (hp->errno); +} + +int +dbm_clearerr(db) + DBM *db; +{ + HTAB *hp; + + hp = (HTAB *)db->internal; + hp->errno = 0; + return (0); +} + +int +dbm_dirfno(db) + DBM *db; +{ + return(((HTAB *)db->internal)->fp); +} diff --git a/src/util/db2/hash/extern.h b/src/util/db2/hash/extern.h new file mode 100644 index 000000000..dd8a34e8e --- /dev/null +++ b/src/util/db2/hash/extern.h @@ -0,0 +1,76 @@ +/*- + * Copyright (c) 1991, 1993, 1994 + * The Regents of the University of California. All rights reserved. + * + * 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. + * + * @(#)extern.h 8.8 (Berkeley) 11/7/95 + */ + +PAGE16 *__add_bigpage __P((HTAB *, PAGE16 *, indx_t, const u_int8_t)); +PAGE16 *__add_ovflpage __P((HTAB *, PAGE16 *)); +int32_t __addel __P((HTAB *, ITEM_INFO *, + const DBT *, const DBT *, u_int32_t, const u_int8_t)); +u_int32_t __alloc_tmp __P((HTAB*)); +int32_t __big_delete __P((HTAB *, PAGE16 *, indx_t)); +int32_t __big_insert __P((HTAB *, PAGE16 *, const DBT *, const DBT *)); +int32_t __big_keydata __P((HTAB *, PAGE16 *, DBT *, DBT *, int32_t)); +int32_t __big_return __P((HTAB *, ITEM_INFO *, DBT *, int32_t)); +u_int32_t __call_hash __P((HTAB *, int8_t *, int32_t)); +CURSOR *__cursor_creat __P((const DB *)); +int32_t __delete_page __P((HTAB *, PAGE16 *, int32_t)); +int32_t __delpair __P((HTAB *, CURSOR *, ITEM_INFO *)); +int32_t __expand_table __P((HTAB *)); +int32_t __find_bigpair __P((HTAB *, CURSOR *, int8_t *, int32_t)); +void __free_ovflpage __P((HTAB *, PAGE16 *)); +int32_t __get_bigkey __P((HTAB *, PAGE16 *, indx_t, DBT *)); +PAGE16 *__get_buf __P((HTAB *, u_int32_t, int32_t)); +u_int32_t __get_item __P((HTAB *, CURSOR *, DBT *, DBT *, ITEM_INFO *)); +u_int32_t __get_item_done __P((HTAB *, CURSOR *)); +u_int32_t __get_item_first __P((HTAB *, CURSOR *, DBT *, DBT *, ITEM_INFO *)); +u_int32_t __get_item_next __P((HTAB *, CURSOR *, DBT *, DBT *, ITEM_INFO *)); +u_int32_t __get_item_reset __P((HTAB *, CURSOR *)); +PAGE16 *__get_page __P((HTAB *, u_int32_t, int32_t)); +int32_t __ibitmap __P((HTAB *, int32_t, int32_t, int32_t)); +u_int32_t __log2 __P((u_int32_t)); +int32_t __new_page __P((HTAB *, u_int32_t, int32_t)); +void __pgin_routine __P((void *, db_pgno_t, void *)); +void __pgout_routine __P((void *, db_pgno_t, void *)); +u_int32_t __put_buf __P((HTAB *, PAGE16 *, u_int32_t)); +int32_t __put_page __P((HTAB *, PAGE16 *, int32_t, int32_t)); +void __reclaim_tmp __P((HTAB *)); +int32_t __split_page __P((HTAB *, u_int32_t, u_int32_t)); + +/* Default hash routine. */ +extern u_int32_t (*__default_hash) __P((const void *, size_t)); + +#ifdef HASH_STATISTICS +extern long hash_accesses, hash_bigpages, hash_collisions, hash_expansions; +extern long hash_overflow; +#endif diff --git a/src/util/db2/hash/hash.c b/src/util/db2/hash/hash.c new file mode 100644 index 000000000..017138606 --- /dev/null +++ b/src/util/db2/hash/hash.c @@ -0,0 +1,1068 @@ +/*- + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash.c 8.12 (Berkeley) 11/7/95"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/param.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-int.h" +#include "hash.h" +#include "page.h" +#include "extern.h" + +static int32_t flush_meta __P((HTAB *)); +static int32_t hash_access __P((HTAB *, ACTION, DBT *, DBT *)); +static int32_t hash_close __P((DB *)); +static int32_t hash_delete __P((const DB *, const DBT *, u_int32_t)); +static int32_t hash_fd __P((const DB *)); +static int32_t hash_get __P((const DB *, const DBT *, DBT *, u_int32_t)); +static int32_t hash_put __P((const DB *, DBT *, const DBT *, u_int32_t)); +static int32_t hash_seq __P((const DB *, DBT *, DBT *, u_int32_t)); +static int32_t hash_sync __P((const DB *, u_int32_t)); +static int32_t hdestroy __P((HTAB *)); +static int32_t cursor_get __P((const DB *, CURSOR *, DBT *, DBT *, \ + u_int32_t)); +static int32_t cursor_delete __P((const DB *, CURSOR *, u_int32_t)); +static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *)); +static int32_t init_htab __P((HTAB *, int32_t)); +#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN +static void swap_header __P((HTAB *)); +static void swap_header_copy __P((HASHHDR *, HASHHDR *)); +#endif +static u_int32_t hget_header __P((HTAB *, u_int32_t)); +static void hput_header __P((HTAB *)); + +#define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } + +/* Return values */ +#define SUCCESS (0) +#define ERROR (-1) +#define ABNORMAL (1) + +#ifdef HASH_STATISTICS +u_int32_t hash_accesses, hash_collisions, hash_expansions, hash_overflows, + hash_bigpages; +#endif + +/************************** INTERFACE ROUTINES ***************************/ +/* OPEN/CLOSE */ + +extern DB * +__hash_open(file, flags, mode, info, dflags) + const char *file; + int32_t flags, mode, dflags; + const HASHINFO *info; /* Special directives for create */ +{ + struct stat statbuf; + DB *dbp; + DBT mpool_key; + HTAB *hashp; + int32_t bpages, csize, new_table, save_errno, specified_file; + + if ((flags & O_ACCMODE) == O_WRONLY) { + errno = EINVAL; + return (NULL); + } + if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) + return (NULL); + hashp->fp = -1; + + /* set this now, before file goes away... */ + specified_file = (file != NULL); + if (!file) { + file = tmpnam(NULL); + /* store the file name so that we can unlink it later */ + hashp->fname = (char *)file; +#ifdef DEBUG + fprintf(stderr, "Using file name %s.\n", file); +#endif + } + /* + * 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; + hashp->save_file = specified_file && (hashp->flags & O_RDWR); + + new_table = 0; + if (!file || (flags & O_TRUNC) || + (stat(file, &statbuf) && (errno == ENOENT))) { + if (errno == ENOENT) + errno = 0; /* In case someone looks at errno. */ + new_table = 1; + } + if (file) { + if ((hashp->fp = open(file, flags, mode)) == -1) + RETURN_ERROR(errno, error0); + (void)fcntl(hashp->fp, F_SETFD, 1); + } + + /* Process arguments to set up hash table header. */ + 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; + + /* copy metadata from page into header */ + if (hget_header(hashp, + (info && info->bsize ? info->bsize : DEF_BUCKET_SIZE)) != + sizeof(HASHHDR)) + RETURN_ERROR(EFTYPE, error1); + + /* Verify file type, versions and hash function */ + if (hashp->hdr.magic != HASHMAGIC) + RETURN_ERROR(EFTYPE, error1); +#define OLDHASHVERSION 1 + if (hashp->hdr.version != HASHVERSION && + hashp->hdr.version != OLDHASHVERSION) + RETURN_ERROR(EFTYPE, error1); + if (hashp->hash(CHARKEY, sizeof(CHARKEY)) + != hashp->hdr.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. + */ + + /* Read in bitmaps */ + bpages = (hashp->hdr.spares[hashp->hdr.ovfl_point] + + (hashp->hdr.bsize << BYTE_SHIFT) - 1) >> + (hashp->hdr.bshift + BYTE_SHIFT); + + hashp->nmaps = bpages; + (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *)); + } + + /* start up mpool */ + mpool_key.data = (u_int8_t *)file; + mpool_key.size = strlen(file); + + if (info && info->cachesize) + csize = info->cachesize / hashp->hdr.bsize; + else + csize = DEF_CACHESIZE / hashp->hdr.bsize; + hashp->mp = mpool_open(&mpool_key, hashp->fp, hashp->hdr.bsize, csize); + + if (!hashp->mp) + RETURN_ERROR(errno, error1); + mpool_filter(hashp->mp, __pgin_routine, __pgout_routine, hashp); + + /* + * For a new table, set up the bitmaps. + */ + if (new_table && + init_htab(hashp, info && info->nelem ? info->nelem : 1)) + goto error2; + + /* initialize the cursor queue */ + TAILQ_INIT(&hashp->curs_queue); + hashp->seq_cursor = NULL; + + + /* get a chunk of memory for our split buffer */ + hashp->split_buf = (PAGE16 *)malloc(hashp->hdr.bsize); + if (!hashp->split_buf) + goto error2; + + hashp->new_file = new_table; + + if (!(dbp = (DB *)malloc(sizeof(DB)))) + goto error2; + + 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%lx\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 ", (void *)hashp, + "BUCKET SIZE ", hashp->hdr.bsize, + "BUCKET SHIFT ", hashp->hdr.bshift, + "FILL FACTOR ", hashp->hdr.ffactor, + "MAX BUCKET ", hashp->hdr.max_bucket, + "OVFL POINT ", hashp->hdr.ovfl_point, + "LAST FREED ", hashp->hdr.last_freed, + "HIGH MASK ", hashp->hdr.high_mask, + "LOW MASK ", hashp->hdr.low_mask, + "NKEYS ", hashp->hdr.nkeys); +#endif +#ifdef HASH_STATISTICS + hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; + hash_bigpages = 0; +#endif + return (dbp); + +error2: + save_errno = errno; + hdestroy(hashp); + errno = save_errno; + return (NULL); + +error1: + if (hashp != NULL) + (void)close(hashp->fp); + +error0: + free(hashp); + errno = save_errno; + return (NULL); +} + +static int32_t +hash_close(dbp) + DB *dbp; +{ + HTAB *hashp; + int32_t retval; + + if (!dbp) + return (ERROR); + + hashp = (HTAB *)dbp->internal; + retval = hdestroy(hashp); + free(dbp); + return (retval); +} + +static int32_t +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; + HASHINFO *info; +{ + struct stat statbuf; + int32_t nelem; + + nelem = 1; + hashp->hdr.nkeys = 0; + hashp->hdr.lorder = DB_BYTE_ORDER; + hashp->hdr.bsize = DEF_BUCKET_SIZE; + hashp->hdr.bshift = DEF_BUCKET_SHIFT; + hashp->hdr.ffactor = DEF_FFACTOR; + hashp->hash = __default_hash; + memset(hashp->hdr.spares, 0, sizeof(hashp->hdr.spares)); + memset(hashp->hdr.bitmaps, 0, sizeof(hashp->hdr.bitmaps)); + + /* Fix bucket size to be optimal for file system */ + if (file != NULL) { + if (stat(file, &statbuf)) + return (NULL); + hashp->hdr.bsize = statbuf.st_blksize; + hashp->hdr.bshift = __log2(hashp->hdr.bsize); + } + if (info) { + if (info->bsize) { + /* Round pagesize up to power of 2 */ + hashp->hdr.bshift = __log2(info->bsize); + hashp->hdr.bsize = 1 << hashp->hdr.bshift; + if (hashp->hdr.bsize > MAX_BSIZE) { + errno = EINVAL; + return (NULL); + } + } + if (info->ffactor) + hashp->hdr.ffactor = info->ffactor; + if (info->hash) + hashp->hash = info->hash; + if (info->lorder) { + if ((info->lorder != DB_BIG_ENDIAN) && + (info->lorder != DB_LITTLE_ENDIAN)) { + errno = EINVAL; + return (NULL); + } + hashp->hdr.lorder = info->lorder; + } + } + return (hashp); +} + +/* + * Returns 0 on No Error + */ +static int32_t +init_htab(hashp, nelem) + HTAB *hashp; + int32_t nelem; +{ + int32_t l2, nbuckets; + db_pgno_t i; + + /* + * 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->hdr.ffactor + 1; + + l2 = __log2(MAX(nelem, 2)); + nbuckets = 1 << l2; + + hashp->hdr.spares[l2] = l2 + 1; + hashp->hdr.spares[l2 + 1] = l2 + 1; + hashp->hdr.ovfl_point = l2; + hashp->hdr.last_freed = 2; + + hashp->hdr.max_bucket = hashp->hdr.low_mask = nbuckets - 1; + hashp->hdr.high_mask = (nbuckets << 1) - 1; + + /* + * The number of header pages is the size of the header divided by + * the amount of freespace on header pages (the page size - the + * size of 1 integer where the length of the header info on that + * page is stored) plus another page if it didn't divide evenly. + */ + hashp->hdr.hdrpages = + (sizeof(HASHHDR) / (hashp->hdr.bsize - HEADER_OVERHEAD)) + + (((sizeof(HASHHDR) % (hashp->hdr.bsize - HEADER_OVERHEAD)) == 0) + ? 0 : 1); + + /* Create pages for these buckets */ + /* + for (i = 0; i <= hashp->hdr.max_bucket; i++) { + if (__new_page(hashp, (u_int32_t)i, A_BUCKET) != 0) + return (-1); + } + */ + + /* First bitmap page is at: splitpoint l2 page offset 1 */ + if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0)) + return (-1); + + return (0); +} + +/* + * Functions to get/put hash header. We access the file directly. + */ +u_int32_t +hget_header(hashp, page_size) + HTAB *hashp; + u_int32_t page_size; +{ + u_int32_t num_copied, i; + u_int8_t *hdr_dest; + + num_copied = 0; + i = 0; + + hdr_dest = (u_int8_t *)&hashp->hdr; + + /* + * XXX + * This should not be printing to stderr on a "normal" error case. + */ + lseek(hashp->fp, 0, SEEK_SET); + num_copied = read(hashp->fp, hdr_dest, sizeof(HASHHDR)); + if (num_copied != sizeof(HASHHDR)) { + fprintf(stderr, "hash: could not retrieve header"); + return (0); + } +#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN + swap_header(hashp); +#endif + return (num_copied); +} + +void +hput_header(hashp) + HTAB *hashp; +{ + HASHHDR *whdrp; +#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN + HASHHDR whdr; +#endif + u_int32_t num_copied, i; + + num_copied = i = 0; + + whdrp = &hashp->hdr; +#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN + whdrp = &whdr; + swap_header_copy(&hashp->hdr, whdrp); +#endif + + lseek(hashp->fp, 0, SEEK_SET); + num_copied = write(hashp->fp, whdrp, sizeof(HASHHDR)); + if (num_copied != sizeof(HASHHDR)) + (void)fprintf(stderr, "hash: could not write hash header"); + return; +} + +/********************** DESTROY/CLOSE ROUTINES ************************/ + +/* + * Flushes any changes to the file if necessary and destroys the hashp + * structure, freeing all allocated space. + */ +static int32_t +hdestroy(hashp) + HTAB *hashp; +{ + int32_t save_errno; + + save_errno = 0; + +#ifdef HASH_STATISTICS + { int i; + (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, + "hdestroy: big key/data pages %ld\n", hash_bigpages); + (void)fprintf(stderr, + "keys %ld maxp %d\n", hashp->hdr.nkeys, hashp->hdr.max_bucket); + + for (i = 0; i < NCACHED; i++) + (void)fprintf(stderr, + "spares[%d] = %d\n", i, hashp->hdr.spares[i]); + } +#endif + + if (flush_meta(hashp) && !save_errno) + save_errno = errno; + + /* Free the split page */ + if (hashp->split_buf) + free(hashp->split_buf); + + /* Free the big key and big data returns */ + if (hashp->bigkey_buf) + free(hashp->bigkey_buf); + if (hashp->bigdata_buf) + free(hashp->bigdata_buf); + + /* XXX This should really iterate over the cursor queue, but + it's not clear how to do that, and the only cursor a hash + table ever creates is the one used by hash_seq(). Passing + NULL as the first arg is also a kludge, but I know that + it's never used, so I do it. The intent is to plug the + memory leak. Correctness can come later. */ + + if (hashp->seq_cursor) + hashp->seq_cursor->delete(NULL, hashp->seq_cursor, 0); + + /* shut down mpool */ + mpool_sync(hashp->mp); + mpool_close(hashp->mp); + + if (hashp->fp != -1) + (void)close(hashp->fp); + + /* + * *** This may cause problems if hashp->fname is set in any case + * other than the case that we are generating a temporary file name. + * Note that the new version of mpool should support temporary + * files within mpool itself. + */ + if (hashp->fname && !hashp->save_file) { +#ifdef DEBUG + fprintf(stderr, "Unlinking file %s.\n", hashp->fname); +#endif + /* we need to chmod the file to allow it to be deleted... */ + chmod(hashp->fname, 0700); + unlink(hashp->fname); + /* destroy the temporary name */ + tmpnam(NULL); + } + free(hashp); + + if (save_errno) { + errno = save_errno; + return (ERROR); + } + return (SUCCESS); +} + +/* + * Write modified pages to disk + * + * Returns: + * 0 == OK + * -1 ERROR + */ +static int32_t +hash_sync(dbp, flags) + const DB *dbp; + u_int32_t flags; +{ + HTAB *hashp; + + hashp = (HTAB *)dbp->internal; + + /* + * XXX + * Check success/failure conditions. + */ + return (flush_meta(hashp) || mpool_sync(hashp->mp)); +} + +/* + * Returns: + * 0 == OK + * -1 indicates that errno should be set + */ +static int32_t +flush_meta(hashp) + HTAB *hashp; +{ + int32_t i; + + if (!hashp->save_file) + return (0); + hashp->hdr.magic = HASHMAGIC; + hashp->hdr.version = HASHVERSION; + hashp->hdr.h_charkey = hashp->hash(CHARKEY, sizeof(CHARKEY)); + + /* write out metadata */ + hput_header(hashp); + + for (i = 0; i < NCACHED; i++) + if (hashp->mapp[i]) { + if (__put_page(hashp, + (PAGE16 *)hashp->mapp[i], A_BITMAP, 1)) + return (-1); + hashp->mapp[i] = NULL; + } + 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) + */ + +/* *** make sure this is true! */ + +static int32_t +hash_get(dbp, key, data, flag) + const DB *dbp; + const DBT *key; + DBT *data; + u_int32_t flag; +{ + HTAB *hashp; + + hashp = (HTAB *)dbp->internal; + if (flag) { + hashp->errno = errno = EINVAL; + return (ERROR); + } + return (hash_access(hashp, HASH_GET, (DBT *)key, data)); +} + +static int32_t +hash_put(dbp, key, data, flag) + const DB *dbp; + DBT *key; + const DBT *data; + u_int32_t flag; +{ + HTAB *hashp; + + hashp = (HTAB *)dbp->internal; + if (flag && flag != R_NOOVERWRITE) { + hashp->errno = errno = EINVAL; + return (ERROR); + } + if ((hashp->flags & O_ACCMODE) == O_RDONLY) { + hashp->errno = errno = EPERM; + return (ERROR); + } + return (hash_access(hashp, flag == R_NOOVERWRITE ? + HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); +} + +static int32_t +hash_delete(dbp, key, flag) + const DB *dbp; + const DBT *key; + u_int32_t flag; /* Ignored */ +{ + HTAB *hashp; + + hashp = (HTAB *)dbp->internal; + if (flag) { + hashp->errno = errno = EINVAL; + return (ERROR); + } + if ((hashp->flags & O_ACCMODE) == O_RDONLY) { + hashp->errno = errno = EPERM; + return (ERROR); + } + + return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL)); +} + +/* + * Assume that hashp has been set in wrapper routine. + */ +static int32_t +hash_access(hashp, action, key, val) + HTAB *hashp; + ACTION action; + DBT *key, *val; +{ + DBT page_key, page_val; + CURSOR cursor; + ITEM_INFO item_info; + u_int32_t bucket; + u_int32_t num_items; + +#ifdef HASH_STATISTICS + hash_accesses++; +#endif + + num_items = 0; + + /* + * Set up item_info so that we're looking for space to add an item + * as we cycle through the pages looking for the key. + */ + if (action == HASH_PUT || action == HASH_PUTNEW) { + if (ISBIG(key->size + val->size, hashp)) + item_info.seek_size = PAIR_OVERHEAD; + else + item_info.seek_size = key->size + val->size; + } else + item_info.seek_size = 0; + item_info.seek_found_page = 0; + + bucket = __call_hash(hashp, (int8_t *)key->data, key->size); + + cursor.pagep = NULL; + __get_item_reset(hashp, &cursor); + + cursor.bucket = bucket; + while (1) { + __get_item_next(hashp, &cursor, &page_key, &page_val, &item_info); + if (item_info.status == ITEM_ERROR) + return (ABNORMAL); + if (item_info.status == ITEM_NO_MORE) + break; + num_items++; + if (item_info.key_off == BIGPAIR) { + /* + * !!! + * 0 is a valid index. + */ + if (__find_bigpair(hashp, &cursor, (int8_t *)key->data, + key->size) > 0) + goto found; + } else if (key->size == page_key.size && + !memcmp(key->data, page_key.data, key->size)) + goto found; + } +#ifdef HASH_STATISTICS + hash_collisions++; +#endif + __get_item_done(hashp, &cursor); + + /* + * At this point, item_info will list either the last page in + * the chain, or the last page in the chain plus a pgno for where + * to find the first page in the chain with space for the + * item we wish to add. + */ + + /* Not found */ + switch (action) { + case HASH_PUT: + case HASH_PUTNEW: + if (__addel(hashp, &item_info, key, val, num_items, 0)) + return (ERROR); + break; + case HASH_GET: + case HASH_DELETE: + default: + return (ABNORMAL); + } + + if (item_info.caused_expand) + __expand_table(hashp); + return (SUCCESS); + +found: __get_item_done(hashp, &cursor); + + switch (action) { + case HASH_PUTNEW: + /* mpool_put(hashp->mp, pagep, 0); */ + return (ABNORMAL); + case HASH_GET: + if (item_info.key_off == BIGPAIR) { + if (__big_return(hashp, &item_info, val, 0)) + return (ERROR); + } else { + val->data = page_val.data; + val->size = page_val.size; + } + /* *** data may not be available! */ + break; + case HASH_PUT: + if (__delpair(hashp, &cursor, &item_info) || + __addel(hashp, &item_info, key, val, UNKNOWN, 0)) + return (ERROR); + __get_item_done(hashp, &cursor); + if (item_info.caused_expand) + __expand_table(hashp); + break; + case HASH_DELETE: + if (__delpair(hashp, &cursor, &item_info)) + return (ERROR); + break; + default: + abort(); + } + return (SUCCESS); +} + +/* ****************** CURSORS ********************************** */ +CURSOR * +__cursor_creat(dbp) + const DB *dbp; +{ + CURSOR *new_curs; + HTAB *hashp; + + new_curs = (CURSOR *)malloc(sizeof(struct cursor_t)); + if (!new_curs) + return NULL; + new_curs->internal = + (struct item_info *)malloc(sizeof(struct item_info)); + if (!new_curs->internal) { + free(new_curs); + return NULL; + } + new_curs->get = cursor_get; + new_curs->delete = cursor_delete; + + new_curs->bucket = 0; + new_curs->pgno = INVALID_PGNO; + new_curs->ndx = 0; + new_curs->pgndx = 0; + new_curs->pagep = NULL; + + /* place onto queue of cursors */ + hashp = (HTAB *)dbp->internal; + TAILQ_INSERT_TAIL(&hashp->curs_queue, new_curs, queue); + + return new_curs; +} + +int32_t +cursor_get(dbp, cursorp, key, val, flags) + const DB *dbp; + CURSOR *cursorp; + DBT *key, *val; + u_int32_t flags; +{ + HTAB *hashp; + ITEM_INFO item_info; + + hashp = (HTAB *)dbp->internal; + + if (flags && flags != R_FIRST && flags != R_NEXT) { + hashp->errno = errno = EINVAL; + return (ERROR); + } +#ifdef HASH_STATISTICS + hash_accesses++; +#endif + + item_info.seek_size = 0; + + if (flags == R_FIRST) + __get_item_first(hashp, cursorp, key, val, &item_info); + else + __get_item_next(hashp, cursorp, key, val, &item_info); + + /* + * This needs to be changed around. As is, get_item_next advances + * the pointers on the page but this function actually advances + * bucket pointers. This works, since the only other place we + * use get_item_next is in hash_access which only deals with one + * bucket at a time. However, there is the problem that certain other + * functions (such as find_bigpair and delpair) depend on the + * pgndx member of the cursor. Right now, they are using pngdx - 1 + * since indices refer to the __next__ item that is to be fetched + * from the page. This is ugly, as you may have noticed, whoever + * you are. The best solution would be to depend on item_infos to + * deal with _current_ information, and have the cursors only + * deal with _next_ information. In that scheme, get_item_next + * would also advance buckets. Version 3... + */ + + + /* + * Must always enter this loop to do error handling and + * check for big key/data pair. + */ + while (1) { + if (item_info.status == ITEM_OK) { + if (item_info.key_off == BIGPAIR && + __big_keydata(hashp, cursorp->pagep, key, val, + item_info.pgndx)) + return (ABNORMAL); + + break; + } else if (item_info.status != ITEM_NO_MORE) + return (ABNORMAL); + + __put_page(hashp, cursorp->pagep, A_RAW, 0); + cursorp->ndx = cursorp->pgndx = 0; + cursorp->bucket++; + cursorp->pgno = INVALID_PGNO; + cursorp->pagep = NULL; + if (cursorp->bucket > hashp->hdr.max_bucket) + return (ABNORMAL); + __get_item_next(hashp, cursorp, key, val, &item_info); + } + + __get_item_done(hashp, cursorp); + return (0); +} + +int32_t +cursor_delete(dbp, cursor, flags) + const DB *dbp; + CURSOR *cursor; + u_int32_t flags; +{ + /* XXX this is empirically determined, so it might not be completely + correct, but it seems to work. At the very least it fixes + a memory leak */ + + free(cursor->internal); + free(cursor); + + return (0); +} + +static int32_t +hash_seq(dbp, key, val, flag) + const DB *dbp; + DBT *key, *val; + u_int32_t flag; +{ + HTAB *hashp; + + /* + * Seq just uses the default cursor to go sequecing through the + * database. Note that the default cursor is the first in the list. + */ + + hashp = (HTAB *)dbp->internal; + if (!hashp->seq_cursor) + hashp->seq_cursor = __cursor_creat(dbp); + + return (hashp->seq_cursor->get(dbp, hashp->seq_cursor, key, val, flag)); +} + +/********************************* UTILITIES ************************/ + +/* + * Returns: + * 0 ==> OK + * -1 ==> Error + */ +int32_t +__expand_table(hashp) + HTAB *hashp; +{ + u_int32_t old_bucket, new_bucket; + int32_t spare_ndx; + +#ifdef HASH_STATISTICS + hash_expansions++; +#endif + new_bucket = ++hashp->hdr.max_bucket; + old_bucket = (hashp->hdr.max_bucket & hashp->hdr.low_mask); + + /* Get a page for this new bucket */ + if (__new_page(hashp, new_bucket, A_BUCKET) != 0) + return (-1); + + /* + * If the split point is increasing (hdr.max_bucket's log base 2 + * increases), we need to copy the current contents of the spare + * split bucket to the next bucket. + */ + spare_ndx = __log2(hashp->hdr.max_bucket + 1); + if (spare_ndx > hashp->hdr.ovfl_point) { + hashp->hdr.spares[spare_ndx] = hashp->hdr.spares[hashp->hdr.ovfl_point]; + hashp->hdr.ovfl_point = spare_ndx; + } + if (new_bucket > hashp->hdr.high_mask) { + /* Starting a new doubling */ + hashp->hdr.low_mask = hashp->hdr.high_mask; + hashp->hdr.high_mask = new_bucket | hashp->hdr.low_mask; + } + if (BUCKET_TO_PAGE(new_bucket) > MAX_PAGES(hashp)) { + fprintf(stderr, "hash: Cannot allocate new bucket. Pages exhausted.\n"); + return (-1); + } + /* Relocate records to the new bucket */ + return (__split_page(hashp, old_bucket, new_bucket)); +} + +u_int32_t +__call_hash(hashp, k, len) + HTAB *hashp; + int8_t *k; + int32_t len; +{ + int32_t n, bucket; + + n = hashp->hash(k, len); + bucket = n & hashp->hdr.high_mask; + if (bucket > hashp->hdr.max_bucket) + bucket = bucket & hashp->hdr.low_mask; + return (bucket); +} + +#if DB_BYTE_ORDER == DB_LITTLE_ENDIAN +/* + * Hashp->hdr needs to be byteswapped. + */ +static void +swap_header_copy(srcp, destp) + HASHHDR *srcp, *destp; +{ + int32_t i; + + P_32_COPY(srcp->magic, destp->magic); + P_32_COPY(srcp->version, destp->version); + P_32_COPY(srcp->lorder, destp->lorder); + P_32_COPY(srcp->bsize, destp->bsize); + P_32_COPY(srcp->bshift, destp->bshift); + P_32_COPY(srcp->ovfl_point, destp->ovfl_point); + P_32_COPY(srcp->last_freed, destp->last_freed); + P_32_COPY(srcp->max_bucket, destp->max_bucket); + P_32_COPY(srcp->high_mask, destp->high_mask); + P_32_COPY(srcp->low_mask, destp->low_mask); + P_32_COPY(srcp->ffactor, destp->ffactor); + P_32_COPY(srcp->nkeys, destp->nkeys); + P_32_COPY(srcp->hdrpages, destp->hdrpages); + P_32_COPY(srcp->h_charkey, destp->h_charkey); + for (i = 0; i < NCACHED; i++) { + P_32_COPY(srcp->spares[i], destp->spares[i]); + P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); + } +} + +static void +swap_header(hashp) + HTAB *hashp; +{ + HASHHDR *hdrp; + int32_t i; + + hdrp = &hashp->hdr; + + M_32_SWAP(hdrp->magic); + M_32_SWAP(hdrp->version); + M_32_SWAP(hdrp->lorder); + M_32_SWAP(hdrp->bsize); + M_32_SWAP(hdrp->bshift); + M_32_SWAP(hdrp->ovfl_point); + M_32_SWAP(hdrp->last_freed); + M_32_SWAP(hdrp->max_bucket); + M_32_SWAP(hdrp->high_mask); + M_32_SWAP(hdrp->low_mask); + M_32_SWAP(hdrp->ffactor); + M_32_SWAP(hdrp->nkeys); + M_32_SWAP(hdrp->hdrpages); + M_32_SWAP(hdrp->h_charkey); + for (i = 0; i < NCACHED; i++) { + M_32_SWAP(hdrp->spares[i]); + M_16_SWAP(hdrp->bitmaps[i]); + } +} +#endif /* DB_BYTE_ORDER == DB_LITTLE_ENDIAN */ diff --git a/src/util/db2/hash/hash.c.patch b/src/util/db2/hash/hash.c.patch new file mode 100644 index 000000000..b72cc0d26 --- /dev/null +++ b/src/util/db2/hash/hash.c.patch @@ -0,0 +1,109 @@ +*** /tmp/,RCSt1a21714 Wed Apr 3 11:49:15 1996 +--- hash.c Wed Apr 3 08:43:04 1996 +*************** +*** 399,405 + /* Create pages for these buckets */ + /* + for (i = 0; i <= hashp->hdr.max_bucket; i++) { +! if (__new_page(hashp, i, A_BUCKET) != 0) + return (-1); + } + */ + +--- 399,405 ----- + /* Create pages for these buckets */ + /* + for (i = 0; i <= hashp->hdr.max_bucket; i++) { +! if (__new_page(hashp, (u_int32_t)i, A_BUCKET) != 0) + return (-1); + } + */ +*************** +*** 560,567 + * XXX + * Check success/failure conditions. + */ +! mpool_sync(hashp->mp); +! return (0); + } + + /* + +--- 560,566 ----- + * XXX + * Check success/failure conditions. + */ +! return (flush_meta(hashp) || mpool_sync(hashp->mp)); + } + + /* +*************** +*** 585,591 + hput_header(hashp); + + for (i = 0; i < NCACHED; i++) +! if (hashp->mapp[i]) + if (__put_page(hashp, + (PAGE16 *)hashp->mapp[i], A_BITMAP, 1)) + return (-1); + +--- 584,590 ----- + hput_header(hashp); + + for (i = 0; i < NCACHED; i++) +! if (hashp->mapp[i]) { + if (__put_page(hashp, + (PAGE16 *)hashp->mapp[i], A_BITMAP, 1)) + return (-1); +*************** +*** 589,594 + if (__put_page(hashp, + (PAGE16 *)hashp->mapp[i], A_BITMAP, 1)) + return (-1); + return (0); + } + + +--- 588,595 ----- + if (__put_page(hashp, + (PAGE16 *)hashp->mapp[i], A_BITMAP, 1)) + return (-1); ++ hashp->mapp[i] = NULL; ++ } + return (0); + } + +*************** +*** 726,732 + #ifdef HASH_STATISTICS + hash_collisions++; + #endif +- + __get_item_done(hashp, &cursor); + + /* + +--- 727,732 ----- + #ifdef HASH_STATISTICS + hash_collisions++; + #endif + __get_item_done(hashp, &cursor); + + /* +*************** +*** 773,778 + if (__delpair(hashp, &cursor, &item_info) || + __addel(hashp, &item_info, key, val, UNKNOWN, 0)) + return (ERROR); + if (item_info.caused_expand) + __expand_table(hashp); + break; + +--- 773,779 ----- + if (__delpair(hashp, &cursor, &item_info) || + __addel(hashp, &item_info, key, val, UNKNOWN, 0)) + return (ERROR); ++ __get_item_done(hashp, &cursor); + if (item_info.caused_expand) + __expand_table(hashp); + break; diff --git a/src/util/db2/hash/hash.h b/src/util/db2/hash/hash.h new file mode 100644 index 000000000..973d543a8 --- /dev/null +++ b/src/util/db2/hash/hash.h @@ -0,0 +1,196 @@ +/*- + * 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. + * + * @(#)hash.h 8.4 (Berkeley) 11/2/95 + */ + +#include "mpool.h" +#include "db-queue.h" + +/* Operations */ +typedef enum { + HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT +} ACTION; + +/* cursor structure */ +typedef struct cursor_t { + TAILQ_ENTRY(cursor_t) queue; + int (*get) __P((const DB *, struct cursor_t *, DBT *, DBT *, \ + u_int32_t)); + int (*delete) __P((const DB *, struct cursor_t *, u_int32_t)); + db_pgno_t bucket; + db_pgno_t pgno; + indx_t ndx; + indx_t pgndx; + u_int16_t *pagep; + void *internal; +} CURSOR; + + +#define IS_BUCKET(X) ((X) & BUF_BUCKET) +#define IS_VALID(X) (!((X) & BUF_INVALID)) + +/* Hash Table Information */ +typedef struct hashhdr { /* Disk resident portion */ + int32_t magic; /* Magic NO for hash tables */ + int32_t version; /* Version ID */ + int32_t lorder; /* Byte Order */ + int32_t bsize; /* Bucket/Page Size */ + int32_t bshift; /* Bucket shift */ + int32_t ovfl_point; /* Where overflow pages are being allocated */ + int32_t last_freed; /* Last overflow page freed */ + int32_t max_bucket; /* ID of Maximum bucket in use */ + int32_t high_mask; /* Mask to modulo into entire table */ + int32_t low_mask; /* Mask to modulo into lower half of table */ + int32_t ffactor; /* Fill factor */ + int32_t nkeys; /* Number of keys in hash table */ + int32_t hdrpages; /* Size of table header */ + int32_t h_charkey; /* value of hash(CHARKEY) */ +#define NCACHED 32 /* number of bit maps and spare points */ + int32_t spares[NCACHED];/* spare pages for overflow */ + u_int16_t bitmaps[NCACHED]; /* address of overflow page bitmaps */ +} HASHHDR; + +typedef struct htab { /* Memory resident data structure */ + TAILQ_HEAD(_cursor_queue, cursor_t) curs_queue; + HASHHDR hdr; /* Header */ + u_int32_t (*hash) __P((const void *, size_t)); /* Hash Function */ + int32_t flags; /* Flag values */ + int32_t fp; /* File pointer */ + char *fname; /* File path */ + u_int8_t *bigdata_buf; /* Temporary Buffer for BIG data */ + u_int8_t *bigkey_buf; /* Temporary Buffer for BIG keys */ + u_int16_t *split_buf; /* Temporary buffer for splits */ + CURSOR *seq_cursor; /* Cursor used for hash_seq */ + int32_t errno; /* Error Number -- for DBM compatability */ + int32_t new_file; /* Indicates if fd is backing store or no */ + int32_t save_file; /* Indicates whether we need to flush file at + * exit */ + u_int32_t *mapp[NCACHED];/* Pointers to page maps */ + int32_t nmaps; /* Initial number of bitmaps */ + MPOOL *mp; /* mpool for buffer management */ +} HTAB; + +/* + * Constants + */ +#define MAX_BSIZE 65536 /* 2^16 */ +#define MIN_BUFFERS 6 +#define MINHDRSIZE 512 +#define DEF_CACHESIZE 65536 +#define DEF_BUCKET_SIZE 4096 +#define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ +#define DEF_SEGSIZE 256 +#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ +#define DEF_DIRSIZE 256 +#define DEF_FFACTOR 65536 +#define MIN_FFACTOR 4 +#define SPLTMAX 8 +#define CHARKEY "%$sniglet^&" +#define NUMKEY 1038583 +#define BYTE_SHIFT 3 +#define INT32_T_TO_BYTE 2 +#define INT32_T_BYTE_SHIFT 5 +#define ALL_SET ((u_int32_t)0xFFFFFFFF) +#define ALL_CLEAR 0 + +#define PTROF(X) ((BUFHEAD *)((ptr_t)(X)&~0x3)) +#define ISMOD(X) ((ptr_t)(X)&0x1) +#define DOMOD(X) ((X) = (int8_t *)((ptr_t)(X)|0x1)) +#define ISDISK(X) ((ptr_t)(X)&0x2) +#define DODISK(X) ((X) = (int8_t *)((ptr_t)(X)|0x2)) + +#define BITS_PER_MAP 32 + +/* Given the address of the beginning of a big map, clear/set the nth bit */ +#define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) +#define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) +#define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) + +/* Overflow management */ +/* + * Overflow page numbers are allocated per split point. At each doubling of + * the table, we can allocate extra pages. So, an overflow page number has + * the top 5 bits indicate which split point and the lower 11 bits indicate + * which page at that split point is indicated (pages within split points are + * numberered starting with 1). + */ + +#define SPLITSHIFT 11 +#define SPLITMASK 0x7FF +#define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT) +#define OPAGENUM(N) ((N) & SPLITMASK) +#define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O)) + +#define BUCKET_TO_PAGE(B) \ + ((B) + hashp->hdr.hdrpages + ((B) \ + ? hashp->hdr.spares[__log2((B)+1)-1] : 0)) +#define OADDR_TO_PAGE(B) \ + (BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B))) + +#define POW2(N) (1 << (N)) + +#define MAX_PAGES(H) (DB_OFF_T_MAX / (H)->hdr.bsize) + +/* Shorthands for accessing structure */ +#define METADATA_PGNO 0 +#define SPLIT_PGNO 0xFFFF + +typedef struct item_info { + db_pgno_t pgno; + db_pgno_t bucket; + indx_t ndx; + indx_t pgndx; + u_int8_t status; + int32_t seek_size; + db_pgno_t seek_found_page; + indx_t key_off; + indx_t data_off; + u_int8_t caused_expand; +} ITEM_INFO; + + +#define ITEM_ERROR 0 +#define ITEM_OK 1 +#define ITEM_NO_MORE 2 + +#define ITEM_GET_FIRST 0 +#define ITEM_GET_NEXT 1 +#define ITEM_GET_RESET 2 +#define ITEM_GET_DONE 3 +#define ITEM_GET_N 4 + +#define UNKNOWN 0xffffffff /* for num_items */ +#define NO_EXPAND 0xfffffffe diff --git a/src/util/db2/hash/hash_bigkey.c b/src/util/db2/hash/hash_bigkey.c new file mode 100644 index 000000000..689dc3db6 --- /dev/null +++ b/src/util/db2/hash/hash_bigkey.c @@ -0,0 +1,483 @@ +/*- + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_bigkey.c 8.5 (Berkeley) 11/2/95"; +#endif /* LIBC_SCCS and not lint */ + +/* + * 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/types.h> + +#include <stdlib.h> +#include <string.h> + +#ifdef DEBUG +#include <assert.h> +#endif + +#include "db-int.h" +#include "hash.h" +#include "page.h" +#include "extern.h" + +static int32_t collect_key __P((HTAB *, PAGE16 *, int32_t, db_pgno_t *)); +static int32_t collect_data __P((HTAB *, PAGE16 *, int32_t)); + +/* + * Big_insert + * + * You need to do an insert and the key/data pair is greater than + * MINFILL * the bucket size + * + * Returns: + * 0 ==> OK + * -1 ==> ERROR + */ +int32_t +__big_insert(hashp, pagep, key, val) + HTAB *hashp; + PAGE16 *pagep; + const DBT *key, *val; +{ + size_t key_size, val_size; + indx_t key_move_bytes, val_move_bytes; + int8_t *key_data, *val_data, base_page; + + key_data = (int8_t *)key->data; + key_size = key->size; + val_data = (int8_t *)val->data; + val_size = val->size; + + NUM_ENT(pagep) = NUM_ENT(pagep) + 1; + + for (base_page = 1; key_size + val_size;) { + /* Add a page! */ + pagep = + __add_bigpage(hashp, pagep, NUM_ENT(pagep) - 1, base_page); + if (!pagep) + return (-1); + + /* There's just going to be one entry on this page. */ + NUM_ENT(pagep) = 1; + + /* Move the key's data. */ + key_move_bytes = MIN(FREESPACE(pagep), key_size); + /* Mark the page as to how much key & data is on this page. */ + BIGKEYLEN(pagep) = key_move_bytes; + val_move_bytes = + MIN(FREESPACE(pagep) - key_move_bytes, val_size); + BIGDATALEN(pagep) = val_move_bytes; + + /* Note big pages build beginning --> end, not vice versa. */ + if (key_move_bytes) + memmove(BIGKEY(pagep), key_data, key_move_bytes); + if (val_move_bytes) + memmove(BIGDATA(pagep), val_data, val_move_bytes); + + key_size -= key_move_bytes; + key_data += key_move_bytes; + val_size -= val_move_bytes; + val_data += val_move_bytes; + + base_page = 0; + } + __put_page(hashp, pagep, A_RAW, 1); + return (0); +} + +/* + * Called when we need to delete a big pair. + * + * Returns: + * 0 => OK + * -1 => ERROR + */ +int32_t +#ifdef __STDC__ +__big_delete(HTAB *hashp, PAGE16 *pagep, indx_t ndx) +#else +__big_delete(hashp, pagep, ndx) + HTAB *hashp; + PAGE16 *pagep; + u_int32_t ndx; /* Index of big pair on base page. */ +#endif +{ + PAGE16 *last_pagep; + + /* Get first page with big key/data. */ + pagep = __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW); + if (!pagep) + return (-1); + + /* + * Traverse through the pages, freeing the previous one (except + * the first) at each new page. + */ + while (NEXT_PGNO(pagep) != INVALID_PGNO) { + last_pagep = pagep; + pagep = __get_page(hashp, NEXT_PGNO(pagep), A_RAW); + if (!pagep) + return (-1); + __delete_page(hashp, last_pagep, A_OVFL); + } + + /* Free the last page in the chain. */ + __delete_page(hashp, pagep, A_OVFL); + return (0); +} + +/* + * Given a key, indicates whether the big key at cursorp matches the + * given key. + * + * Returns: + * 1 = Found! + * 0 = Key not found + * -1 error + */ +int32_t +__find_bigpair(hashp, cursorp, key, size) + HTAB *hashp; + CURSOR *cursorp; + int8_t *key; + int32_t size; +{ + PAGE16 *pagep, *hold_pagep; + db_pgno_t next_pgno; + int32_t ksize; + u_int16_t bytes; + int8_t *kkey; + + ksize = size; + kkey = key; + bytes = 0; + + hold_pagep = NULL; + /* Chances are, hashp->cpage is the base page. */ + if (cursorp->pagep) + pagep = hold_pagep = cursorp->pagep; + else { + pagep = __get_page(hashp, cursorp->pgno, A_RAW); + if (!pagep) + return (-1); + } + + /* + * Now, get the first page with the big stuff on it. + * + * XXX + * KLUDGE: we know that cursor is looking at the _next_ item, so + * we have to look at pgndx - 1. + */ + next_pgno = OADDR_TO_PAGE(DATA_OFF(pagep, (cursorp->pgndx - 1))); + if (!hold_pagep) + __put_page(hashp, pagep, A_RAW, 0); + pagep = __get_page(hashp, next_pgno, A_RAW); + if (!pagep) + return (-1); + + /* While there are both keys to compare. */ + while ((ksize > 0) && (BIGKEYLEN(pagep))) { + if (ksize < KEY_OFF(pagep, 0) || + memcmp(BIGKEY(pagep), kkey, BIGKEYLEN(pagep))) { + __put_page(hashp, pagep, A_RAW, 0); + return (0); + } + kkey += BIGKEYLEN(pagep); + ksize -= BIGKEYLEN(pagep); + if (NEXT_PGNO(pagep) != INVALID_PGNO) { + next_pgno = NEXT_PGNO(pagep); + __put_page(hashp, pagep, A_RAW, 0); + pagep = __get_page(hashp, next_pgno, A_RAW); + if (!pagep) + return (-1); + } + } + __put_page(hashp, pagep, A_RAW, 0); +#ifdef DEBUG + assert(ksize >= 0); +#endif + if (ksize != 0) { +#ifdef HASH_STATISTICS + ++hash_collisions; +#endif + return (0); + } else + return (1); +} + +/* + * Fill in the key and data for this big pair. + */ +int32_t +__big_keydata(hashp, pagep, key, val, ndx) + HTAB *hashp; + PAGE16 *pagep; + DBT *key, *val; + int32_t ndx; +{ + ITEM_INFO ii; + PAGE16 *key_pagep; + db_pgno_t last_page; + + key_pagep = + __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW); + if (!key_pagep) + return (-1); + key->size = collect_key(hashp, key_pagep, 0, &last_page); + key->data = hashp->bigkey_buf; + __put_page(hashp, key_pagep, A_RAW, 0); + + if (key->size == -1) + return (-1); + + /* Create an item_info to direct __big_return to the beginning pgno. */ + ii.pgno = last_page; + return (__big_return(hashp, &ii, val, 1)); +} + +/* + * Return the big key on page, ndx. + */ +int32_t +#ifdef __STDC__ +__get_bigkey(HTAB *hashp, PAGE16 *pagep, indx_t ndx, DBT *key) +#else +__get_bigkey(hashp, pagep, ndx, key) + HTAB *hashp; + PAGE16 *pagep; + u_int32_t ndx; + DBT *key; +#endif +{ + PAGE16 *key_pagep; + + key_pagep = + __get_page(hashp, OADDR_TO_PAGE(DATA_OFF(pagep, ndx)), A_RAW); + if (!pagep) + return (-1); + key->size = collect_key(hashp, key_pagep, 0, NULL); + key->data = hashp->bigkey_buf; + + __put_page(hashp, key_pagep, A_RAW, 0); + + return (0); +} + +/* + * Return the big key and data indicated in item_info. + */ +int32_t +__big_return(hashp, item_info, val, on_bigkey_page) + HTAB *hashp; + ITEM_INFO *item_info; + DBT *val; + int32_t on_bigkey_page; +{ + PAGE16 *pagep; + db_pgno_t next_pgno; + + if (!on_bigkey_page) { + /* Get first page with big pair on it. */ + pagep = __get_page(hashp, + OADDR_TO_PAGE(item_info->data_off), A_RAW); + if (!pagep) + return (-1); + } else { + pagep = __get_page(hashp, item_info->pgno, A_RAW); + if (!pagep) + return (-1); + } + + /* Traverse through the bigkey pages until a page with data is found. */ + while (!BIGDATALEN(pagep)) { + next_pgno = NEXT_PGNO(pagep); + __put_page(hashp, pagep, A_RAW, 0); + pagep = __get_page(hashp, next_pgno, A_RAW); + if (!pagep) + return (-1); + } + + val->size = collect_data(hashp, pagep, 0); + if (val->size < 1) + return (-1); + val->data = (void *)hashp->bigdata_buf; + + __put_page(hashp, pagep, A_RAW, 0); + return (0); +} + +/* + * Given a page with a big key on it, traverse through the pages counting data + * length, and collect all of the data on the way up. Store the key in + * hashp->bigkey_buf. last_page indicates to the calling function what the + * last page with key on it is; this will help if you later want to retrieve + * the data portion. + * + * Does the work for __get_bigkey. + * + * Return total length of data; -1 if error. + */ +static int32_t +collect_key(hashp, pagep, len, last_page) + HTAB *hashp; + PAGE16 *pagep; + int32_t len; + db_pgno_t *last_page; +{ + PAGE16 *next_pagep; + int32_t totlen, retval; + db_pgno_t next_pgno; +#ifdef DEBUG + db_pgno_t save_addr; +#endif + + /* If this is the last page with key. */ + if (BIGDATALEN(pagep)) { + totlen = len + BIGKEYLEN(pagep); + if (hashp->bigkey_buf) + free(hashp->bigkey_buf); + hashp->bigkey_buf = (char *)malloc(totlen); + if (!hashp->bigkey_buf) + return (-1); + memcpy(hashp->bigkey_buf + len, + BIGKEY(pagep), BIGKEYLEN(pagep)); + if (last_page) + *last_page = ADDR(pagep); + return (totlen); + } + + /* Key filled up all of last key page, so we've gone 1 too far. */ + if (BIGKEYLEN(pagep) == 0) { + if (hashp->bigkey_buf) + free(hashp->bigkey_buf); + hashp->bigkey_buf = (char *)malloc(len); + return (hashp->bigkey_buf ? len : -1); + } + totlen = len + BIGKEYLEN(pagep); + + /* Set pagep to the next page in the chain. */ + if (last_page) + *last_page = ADDR(pagep); + next_pgno = NEXT_PGNO(pagep); + next_pagep = __get_page(hashp, next_pgno, A_RAW); + if (!next_pagep) + return (-1); +#ifdef DEBUG + save_addr = ADDR(pagep); +#endif + retval = collect_key(hashp, next_pagep, totlen, last_page); + +#ifdef DEBUG + assert(save_addr == ADDR(pagep)); +#endif + memcpy(hashp->bigkey_buf + len, BIGKEY(pagep), BIGKEYLEN(pagep)); + __put_page(hashp, next_pagep, A_RAW, 0); + + return (retval); +} + +/* + * Given a page with big data on it, recur through the pages counting data + * length, and collect all of the data on the way up. Store the data in + * hashp->bigdata_buf. + * + * Does the work for __big_return. + * + * Return total length of data; -1 if error. + */ +static int32_t +collect_data(hashp, pagep, len) + HTAB *hashp; + PAGE16 *pagep; + int32_t len; +{ + PAGE16 *next_pagep; + int32_t totlen, retval; + db_pgno_t next_pgno; +#ifdef DEBUG + db_pgno_t save_addr; +#endif + + /* If there is no next page. */ + if (NEXT_PGNO(pagep) == INVALID_PGNO) { + if (hashp->bigdata_buf) + free(hashp->bigdata_buf); + totlen = len + BIGDATALEN(pagep); + hashp->bigdata_buf = (char *)malloc(totlen); + if (!hashp->bigdata_buf) + return (-1); + memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep), + BIGDATA(pagep), BIGDATALEN(pagep)); + return (totlen); + } + totlen = len + BIGDATALEN(pagep); + + /* Set pagep to the next page in the chain. */ + next_pgno = NEXT_PGNO(pagep); + next_pagep = __get_page(hashp, next_pgno, A_RAW); + if (!next_pagep) + return (-1); + +#ifdef DEBUG + save_addr = ADDR(pagep); +#endif + retval = collect_data(hashp, next_pagep, totlen); +#ifdef DEBUG + assert(save_addr == ADDR(pagep)); +#endif + memcpy(hashp->bigdata_buf + totlen - BIGDATALEN(pagep), + BIGDATA(pagep), BIGDATALEN(pagep)); + __put_page(hashp, next_pagep, A_RAW, 0); + + return (retval); +} diff --git a/src/util/db2/hash/hash_debug.c b/src/util/db2/hash/hash_debug.c new file mode 100644 index 000000000..ed99c6932 --- /dev/null +++ b/src/util/db2/hash/hash_debug.c @@ -0,0 +1,106 @@ +/*- + * Copyright (c) 1995 + * The President and Fellows of Harvard University + * + * This code is derived from software contributed to Harvard by + * Jeremy Rassen. + * + * 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) +static char sccsid[] = "@(#)hash_debug.c 8.4 (Berkeley) 11/7/95"; +#endif /* LIBC_SCCS and not lint */ + +#ifdef DEBUG +/* + * PACKAGE: hashing + * + * DESCRIPTION: + * Debug routines. + * + * ROUTINES: + * + * External + * __dump_bucket + */ +#include <stdio.h> + +#include "db-int.h" +#include "hash.h" +#include "page.h" +#include "extern.h" +#include "compat.h" + +void +__dump_bucket(hashp, bucket) + HTAB *hashp; + u_int32_t bucket; +{ + CURSOR cursor; + DBT key, val; + ITEM_INFO item_info; + int var; + char *cp; + + cursor.pagep = NULL; + item_info.seek_size = 0; + item_info.seek_found_page = 0; + + __get_item_reset(hashp, &cursor); + + cursor.bucket = bucket; + for (;;) { + __get_item_next(hashp, &cursor, &key, &val, &item_info); + if (item_info.status == ITEM_ERROR) { + (void)printf("get_item_next returned error\n"); + break; + } else if (item_info.status == ITEM_NO_MORE) + break; + + if (item_info.key_off == BIGPAIR) { + if (__big_keydata(hashp, cursor.pagep, &key, &val, + item_info.pgndx)) { + (void)printf("__big_keydata returned error\n"); + break; + } + } + + if (key.size == sizeof(int)) { + memcpy(&var, key.data, sizeof(int)); + (void)printf("%d\n", var); + } else { + for (cp = (char *)key.data; key.size--; cp++) + (void)printf("%c", *cp); + (void)printf("\n"); + } + } + __get_item_done(hashp, &cursor); +} +#endif /* DEBUG */ diff --git a/src/util/db2/hash/hash_func.c b/src/util/db2/hash/hash_func.c new file mode 100644 index 000000000..efa2a2843 --- /dev/null +++ b/src/util/db2/hash/hash_func.c @@ -0,0 +1,196 @@ +/*- + * 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. + * + * 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) +static char sccsid[] = "@(#)hash_func.c 8.4 (Berkeley) 11/7/95"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> + +#include "db-int.h" +#include "hash.h" +#include "page.h" +#include "extern.h" + +static u_int32_t hash1 __P((const void *, size_t)); +static u_int32_t hash2 __P((const void *, size_t)); +static u_int32_t hash3 __P((const void *, size_t)); +static u_int32_t hash4 __P((const void *, size_t)); + +/* Default hash function. */ +u_int32_t (*__default_hash) __P((const void *, size_t)) = hash4; + +/* + * Assume that we've already split the bucket to which this key hashes, + * calculate that bucket, and check that in fact we did already split it. + * + * EJB's original hsearch hash. + */ +#define PRIME1 37 +#define PRIME2 1048583 + +u_int32_t +hash1(key, len) + const void *key; + size_t len; +{ + u_int32_t h; + u_int8_t *k; + + h = 0; + k = (u_int8_t *)key; + /* Convert string to integer */ + while (len--) + h = h * PRIME1 ^ (*k++ - ' '); + h %= PRIME2; + return (h); +} + +/* + * Phong Vo's linear congruential hash + */ +#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) + +u_int32_t +hash2(key, len) + const void *key; + size_t len; +{ + u_int32_t h; + u_int8_t *e, c, *k; + + k = (u_int8_t *)key; + e = k + len; + for (h = 0; k != e;) { + c = *k++; + if (!c && k > e) + break; + dcharhash(h, c); + } + return (h); +} + +/* + * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte + * units. On the first time through the loop we get the "leftover bytes" + * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle + * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If + * this routine is heavily used enough, it's worth the ugly coding. + * + * Ozan Yigit's original sdbm hash. + */ +u_int32_t +hash3(key, len) + const void *key; + size_t len; +{ + u_int32_t n, loop; + u_int8_t *k; + +#define HASHC n = *k++ + 65599 * n + + n = 0; + k = (u_int8_t *)key; + if (len > 0) { + loop = (len + 8 - 1) >> 3; + + switch (len & (8 - 1)) { + case 0: + do { /* All fall throughs */ + HASHC; + case 7: + HASHC; + case 6: + HASHC; + case 5: + HASHC; + case 4: + HASHC; + case 3: + HASHC; + case 2: + HASHC; + case 1: + HASHC; + } while (--loop); + } + + } + return (n); +} + +/* Chris Torek's hash function. */ +u_int32_t +hash4(key, len) + const void *key; + size_t len; +{ + u_int32_t h, loop; + u_int8_t *k; + +#define HASH4a h = (h << 5) - h + *k++; +#define HASH4b h = (h << 5) + h + *k++; +#define HASH4 HASH4b + + h = 0; + k = (u_int8_t *)key; + if (len > 0) { + loop = (len + 8 - 1) >> 3; + + switch (len & (8 - 1)) { + case 0: + do { /* All fall throughs */ + HASH4; + case 7: + HASH4; + case 6: + HASH4; + case 5: + HASH4; + case 4: + HASH4; + case 3: + HASH4; + case 2: + HASH4; + case 1: + HASH4; + } while (--loop); + } + + } + return (h); +} diff --git a/src/util/db2/hash/hash_log2.c b/src/util/db2/hash/hash_log2.c new file mode 100644 index 000000000..8604945e8 --- /dev/null +++ b/src/util/db2/hash/hash_log2.c @@ -0,0 +1,52 @@ +/*- + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_log2.c 8.4 (Berkeley) 11/7/95"; +#endif /* LIBC_SCCS and not lint */ + +#include "db-int.h" + +u_int32_t +__log2(num) + u_int32_t num; +{ + u_int32_t i, limit; + + limit = 1; + for (i = 0; limit < num; limit = limit << 1, i++); + return (i); +} diff --git a/src/util/db2/hash/hash_page.c b/src/util/db2/hash/hash_page.c new file mode 100644 index 000000000..8622075d1 --- /dev/null +++ b/src/util/db2/hash/hash_page.c @@ -0,0 +1,1380 @@ +/*- + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)hash_page.c 8.11 (Berkeley) 11/7/95"; +#endif /* LIBC_SCCS and not lint */ + +/* + * PACKAGE: hashing + * + * DESCRIPTION: + * Page manipulation for hashing package. + * + * ROUTINES: + * + * External + * __get_page + * __add_ovflpage + * Internal + * overflow_page + * open_temp + */ + +#include <sys/types.h> + +#ifdef DEBUG +#include <assert.h> +#endif +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include "db-int.h" +#include "hash.h" +#include "page.h" +#include "extern.h" + +static int32_t add_bigptr __P((HTAB *, ITEM_INFO *, indx_t)); +static u_int32_t *fetch_bitmap __P((HTAB *, int32_t)); +static u_int32_t first_free __P((u_int32_t)); +static indx_t next_realkey __P((PAGE16 *, indx_t)); +static u_int16_t overflow_page __P((HTAB *)); +static void page_init __P((HTAB *, PAGE16 *, db_pgno_t, u_int8_t)); +static indx_t prev_realkey __P((PAGE16 *, indx_t)); +static void putpair __P((PAGE8 *, const DBT *, const DBT *)); +static void swap_page_header_in __P((PAGE16 *)); +static void swap_page_header_out __P((PAGE16 *)); + +#ifdef DEBUG_SLOW +static void account_page(HTAB *, db_pgno_t, int); +#endif + +u_int32_t +__get_item(hashp, cursorp, key, val, item_info) + HTAB *hashp; + CURSOR *cursorp; + DBT *key, *val; + ITEM_INFO *item_info; +{ + db_pgno_t next_pgno; + int32_t i; + + /* Check if we need to get a page. */ + if (!cursorp->pagep) { + if (cursorp->pgno == INVALID_PGNO) { + cursorp->pagep = + __get_page(hashp, cursorp->bucket, A_BUCKET); + cursorp->pgno = ADDR(cursorp->pagep); + cursorp->ndx = 0; + cursorp->pgndx = 0; + } else + cursorp->pagep = + __get_page(hashp, cursorp->pgno, A_RAW); + if (!cursorp->pagep) { + item_info->status = ITEM_ERROR; + return (-1); + } + } + if (item_info->seek_size && + FREESPACE(cursorp->pagep) > item_info->seek_size) + item_info->seek_found_page = cursorp->pgno; + + if (cursorp->pgndx == NUM_ENT(cursorp->pagep)) { + /* Fetch next page. */ + if (NEXT_PGNO(cursorp->pagep) == INVALID_PGNO) { + item_info->status = ITEM_NO_MORE; + return (-1); + } + next_pgno = NEXT_PGNO(cursorp->pagep); + cursorp->pgndx = 0; + __put_page(hashp, cursorp->pagep, A_RAW, 0); + cursorp->pagep = __get_page(hashp, next_pgno, A_RAW); + if (!cursorp->pagep) { + item_info->status = ITEM_ERROR; + return (-1); + } + cursorp->pgno = next_pgno; + } + if (KEY_OFF(cursorp->pagep, cursorp->pgndx) != BIGPAIR) { + if ((i = prev_realkey(cursorp->pagep, cursorp->pgndx)) == + cursorp->pgndx) + key->size = hashp->hdr.bsize - + KEY_OFF(cursorp->pagep, cursorp->pgndx); + else + key->size = DATA_OFF(cursorp->pagep, i) - + KEY_OFF(cursorp->pagep, cursorp->pgndx); + } + + /* + * All of this information will be set incorrectly for big keys, but + * it will be ignored anyway. + */ + val->size = KEY_OFF(cursorp->pagep, cursorp->pgndx) - + DATA_OFF(cursorp->pagep, cursorp->pgndx); + key->data = KEY(cursorp->pagep, cursorp->pgndx); + val->data = DATA(cursorp->pagep, cursorp->pgndx); + item_info->pgno = cursorp->pgno; + item_info->bucket = cursorp->bucket; + item_info->ndx = cursorp->ndx; + item_info->pgndx = cursorp->pgndx; + item_info->key_off = KEY_OFF(cursorp->pagep, cursorp->pgndx); + item_info->data_off = DATA_OFF(cursorp->pagep, cursorp->pgndx); + item_info->status = ITEM_OK; + + return (0); +} + +u_int32_t +__get_item_reset(hashp, cursorp) + HTAB *hashp; + CURSOR *cursorp; +{ + if (cursorp->pagep) + __put_page(hashp, cursorp->pagep, A_RAW, 0); + cursorp->pagep = NULL; + cursorp->bucket = -1; + cursorp->ndx = 0; + cursorp->pgndx = 0; + cursorp->pgno = INVALID_PGNO; + return (0); +} + +u_int32_t +__get_item_done(hashp, cursorp) + HTAB *hashp; + CURSOR *cursorp; +{ + if (cursorp->pagep) + __put_page(hashp, cursorp->pagep, A_RAW, 0); + cursorp->pagep = NULL; + + /* + * We don't throw out the page number since we might want to + * continue getting on this page. + */ + return (0); +} + +u_int32_t +__get_item_first(hashp, cursorp, key, val, item_info) + HTAB *hashp; + CURSOR *cursorp; + DBT *key, *val; + ITEM_INFO *item_info; +{ + __get_item_reset(hashp, cursorp); + cursorp->bucket = 0; + return (__get_item_next(hashp, cursorp, key, val, item_info)); +} + +/* + * Returns a pointer to key/data pair on a page. In the case of bigkeys, + * just returns the page number and index of the bigkey pointer pair. + */ +u_int32_t +__get_item_next(hashp, cursorp, key, val, item_info) + HTAB *hashp; + CURSOR *cursorp; + DBT *key, *val; + ITEM_INFO *item_info; +{ + int stat; + + stat = __get_item(hashp, cursorp, key, val, item_info); + cursorp->ndx++; + cursorp->pgndx++; + return (stat); +} + +/* + * Put a non-big pair on a page. + */ +static void +putpair(p, key, val) + PAGE8 *p; + const DBT *key, *val; +{ + u_int16_t *pagep, n, off; + + pagep = (PAGE16 *)p; + + /* Items on the page are 0-indexed. */ + n = NUM_ENT(pagep); + off = OFFSET(pagep) - key->size + 1; + memmove(p + off, key->data, key->size); + KEY_OFF(pagep, n) = off; + + off -= val->size; + memmove(p + off, val->data, val->size); + DATA_OFF(pagep, n) = off; + + /* Adjust page info. */ + NUM_ENT(pagep) = n + 1; + OFFSET(pagep) = off - 1; +} + +/* + * Returns the index of the next non-bigkey pair after n on the page. + * Returns -1 if there are no more non-big things on the page. + */ +indx_t +#ifdef __STDC__ +next_realkey(PAGE16 * pagep, indx_t n) +#else +next_realkey(pagep, n) + PAGE16 *pagep; + u_int32_t n; +#endif +{ + indx_t i; + + for (i = n + 1; i < NUM_ENT(pagep); i++) + if (KEY_OFF(pagep, i) != BIGPAIR) + return (i); + return (-1); +} + +/* + * Returns the index of the previous non-bigkey pair after n on the page. + * Returns n if there are no previous non-big things on the page. + */ +static indx_t +#ifdef __STDC__ +prev_realkey(PAGE16 * pagep, indx_t n) +#else +prev_realkey(pagep, n) + PAGE16 *pagep; + u_int32_t n; +#endif +{ + int32_t i; + + /* Need a signed value to do the compare properly. */ + for (i = n - 1; i > -1; i--) + if (KEY_OFF(pagep, i) != BIGPAIR) + return (i); + return (n); +} + +/* + * Returns: + * 0 OK + * -1 error + */ +extern int32_t +__delpair(hashp, cursorp, item_info) + HTAB *hashp; + CURSOR *cursorp; + ITEM_INFO *item_info; +{ + PAGE16 *pagep; + indx_t ndx; + short check_ndx; + int16_t delta, len, next_key; + int32_t n; + u_int8_t *src, *dest; + + ndx = cursorp->pgndx; + if (!cursorp->pagep) { + pagep = __get_page(hashp, cursorp->pgno, A_RAW); + if (!pagep) + return (-1); + /* + * KLUGE: pgndx has gone one too far, because cursor points + * to the _next_ item. Use pgndx - 1. + */ + --ndx; + } else + pagep = cursorp->pagep; +#ifdef DEBUG + assert(ADDR(pagep) == cursorp->pgno); +#endif + + if (KEY_OFF(pagep, ndx) == BIGPAIR) { + delta = 0; + __big_delete(hashp, pagep, ndx); + } else { + /* + * Compute "delta", the amount we have to shift all of the + * offsets. To find the delta, we need to make sure that + * we aren't looking at the DATA_OFF of a big/keydata pair. + */ + for (check_ndx = (short)(ndx - 1); + check_ndx >= 0 && KEY_OFF(pagep, check_ndx) == BIGPAIR; + check_ndx--); + if (check_ndx < 0) + delta = hashp->hdr.bsize - DATA_OFF(pagep, ndx); + else + delta = + DATA_OFF(pagep, check_ndx) - DATA_OFF(pagep, ndx); + + /* + * The hard case: we want to remove something other than + * the last item on the page. We need to shift data and + * offsets down. + */ + if (ndx != NUM_ENT(pagep) - 1) { + /* + * Move the data: src is the address of the last data + * item on the page. + */ + src = (u_int8_t *)pagep + OFFSET(pagep) + 1; + /* + * Length is the distance between where to start + * deleting and end of the data on the page. + */ + len = DATA_OFF(pagep, ndx) - (OFFSET(pagep) + 1); + /* + * Dest is the location of the to-be-deleted item + * occupied - length. + */ + if (check_ndx < 0) + dest = + (u_int8_t *)pagep + hashp->hdr.bsize - len; + else + dest = (u_int8_t *)pagep + + DATA_OFF(pagep, (check_ndx)) - len; + memmove(dest, src, len); + } + } + + /* Adjust the offsets. */ + for (n = ndx; n < NUM_ENT(pagep) - 1; n++) + if (KEY_OFF(pagep, (n + 1)) != BIGPAIR) { + next_key = next_realkey(pagep, n); +#ifdef DEBUG + assert(next_key != -1); +#endif + KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1)) + delta; + DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1)) + delta; + } else { + KEY_OFF(pagep, n) = KEY_OFF(pagep, (n + 1)); + DATA_OFF(pagep, n) = DATA_OFF(pagep, (n + 1)); + } + + /* Adjust page metadata. */ + OFFSET(pagep) = OFFSET(pagep) + delta; + NUM_ENT(pagep) = NUM_ENT(pagep) - 1; + + --hashp->hdr.nkeys; + + /* Is this page now an empty overflow page? If so, free it. */ + if (TYPE(pagep) == HASH_OVFLPAGE && NUM_ENT(pagep) == 0) { + PAGE16 *empty_page; + db_pgno_t to_find, next_pgno, link_page; + + /* + * We need to go back to the first page in the chain and + * look for this page so that we can update the previous + * page's NEXT_PGNO field. + */ + to_find = ADDR(pagep); + empty_page = pagep; + link_page = NEXT_PGNO(empty_page); + pagep = __get_page(hashp, item_info->bucket, A_BUCKET); + if (!pagep) + return (-1); + while (NEXT_PGNO(pagep) != to_find) { + next_pgno = NEXT_PGNO(pagep); +#ifdef DEBUG + assert(next_pgno != INVALID_PGNO); +#endif + __put_page(hashp, pagep, A_RAW, 0); + pagep = __get_page(hashp, next_pgno, A_RAW); + if (!pagep) + return (-1); + } + + /* + * At this point, pagep should point to the page before the + * page to be deleted. + */ + NEXT_PGNO(pagep) = link_page; + if (item_info->pgno == to_find) { + item_info->pgno = ADDR(pagep); + item_info->pgndx = NUM_ENT(pagep); + item_info->seek_found_page = ADDR(pagep); + } + __delete_page(hashp, empty_page, A_OVFL); + } + __put_page(hashp, pagep, A_RAW, 1); + + return (0); +} + +extern int32_t +__split_page(hashp, obucket, nbucket) + HTAB *hashp; + u_int32_t obucket, nbucket; +{ + DBT key, val; + ITEM_INFO old_ii, new_ii; + PAGE16 *old_pagep, *temp_pagep; + db_pgno_t next_pgno; + int32_t off; + u_int16_t n; + int8_t base_page; + + off = hashp->hdr.bsize; + old_pagep = __get_page(hashp, obucket, A_BUCKET); + + base_page = 1; + + temp_pagep = hashp->split_buf; + memcpy(temp_pagep, old_pagep, hashp->hdr.bsize); + + page_init(hashp, old_pagep, ADDR(old_pagep), HASH_PAGE); + __put_page(hashp, old_pagep, A_RAW, 1); + + old_ii.pgno = BUCKET_TO_PAGE(obucket); + new_ii.pgno = BUCKET_TO_PAGE(nbucket); + old_ii.bucket = obucket; + new_ii.bucket = nbucket; + old_ii.seek_found_page = new_ii.seek_found_page = 0; + + while (temp_pagep != 0) { + off = hashp->hdr.bsize; + for (n = 0; n < NUM_ENT(temp_pagep); n++) { + if (KEY_OFF(temp_pagep, n) == BIGPAIR) { + __get_bigkey(hashp, temp_pagep, n, &key); + if (__call_hash(hashp, + key.data, key.size) == obucket) + add_bigptr(hashp, &old_ii, + DATA_OFF(temp_pagep, n)); + else + add_bigptr(hashp, &new_ii, + DATA_OFF(temp_pagep, n)); + } else { + key.size = off - KEY_OFF(temp_pagep, n); + key.data = KEY(temp_pagep, n); + off = KEY_OFF(temp_pagep, n); + val.size = off - DATA_OFF(temp_pagep, n); + val.data = DATA(temp_pagep, n); + if (__call_hash(hashp, + key.data, key.size) == obucket) + __addel(hashp, &old_ii, &key, &val, + NO_EXPAND, 1); + else + __addel(hashp, &new_ii, &key, &val, + NO_EXPAND, 1); + off = DATA_OFF(temp_pagep, n); + } + } + next_pgno = NEXT_PGNO(temp_pagep); + + /* Clear temp_page; if it's an overflow page, free it. */ + if (!base_page) + __delete_page(hashp, temp_pagep, A_OVFL); + else + base_page = 0; + if (next_pgno != INVALID_PGNO) + temp_pagep = __get_page(hashp, next_pgno, A_RAW); + else + break; + } + return (0); +} + +/* + * Add the given pair to the page. + * + * + * Returns: + * 0 ==> OK + * -1 ==> failure + */ +extern int32_t +#ifdef __STDC__ +__addel(HTAB *hashp, ITEM_INFO *item_info, const DBT *key, const DBT *val, + u_int32_t num_items, const u_int8_t expanding) +#else +__addel(hashp, item_info, key, val, num_items, expanding) + HTAB *hashp; + ITEM_INFO *item_info; + const DBT *key, *val; + u_int32_t num_items; + const u_int32_t expanding; +#endif +{ + PAGE16 *pagep; + int32_t do_expand; + db_pgno_t next_pgno; + + do_expand = 0; + + pagep = __get_page(hashp, + item_info->seek_found_page != 0 ? + item_info->seek_found_page : item_info->pgno, A_RAW); + if (!pagep) + return (-1); + + /* Advance to first page in chain with room for item. */ + while (NUM_ENT(pagep) && NEXT_PGNO(pagep) != INVALID_PGNO) { + /* + * This may not be the end of the chain, but the pair may fit + * anyway. + */ + if (ISBIG(PAIRSIZE(key, val), hashp) && BIGPAIRFITS(pagep)) + break; + if (PAIRFITS(pagep, key, val)) + break; + next_pgno = NEXT_PGNO(pagep); + __put_page(hashp, pagep, A_RAW, 0); + pagep = (PAGE16 *)__get_page(hashp, next_pgno, A_RAW); + if (!pagep) + return (-1); + } + + if ((ISBIG(PAIRSIZE(key, val), hashp) && + !BIGPAIRFITS(pagep)) || + (!ISBIG(PAIRSIZE(key, val), hashp) && + !PAIRFITS(pagep, key, val))) { + do_expand = 1; + pagep = __add_ovflpage(hashp, pagep); + if (!pagep) + return (-1); + + if ((ISBIG(PAIRSIZE(key, val), hashp) && + !BIGPAIRFITS(pagep)) || + (!ISBIG(PAIRSIZE(key, val), hashp) && + !PAIRFITS(pagep, key, val))) { + __put_page(hashp, pagep, A_RAW, 0); + return (-1); + } + } + + /* At this point, we know the page fits, so we just add it */ + + if (ISBIG(PAIRSIZE(key, val), hashp)) { + if (__big_insert(hashp, pagep, key, val)) + return (-1); + } else { + putpair((PAGE8 *)pagep, key, val); + } + + /* + * For splits, we are going to update item_info's page number + * field, so that we can easily return to the same page the + * next time we come in here. For other operations, this shouldn't + * matter, since adds are the last thing that happens before we + * return to the user program. + */ + item_info->pgno = ADDR(pagep); + + if (!expanding) + hashp->hdr.nkeys++; + + /* Kludge: if this is a big page, then it's already been put. */ + if (!ISBIG(PAIRSIZE(key, val), hashp)) + __put_page(hashp, pagep, A_RAW, 1); + + if (expanding) + item_info->caused_expand = 0; + else + switch (num_items) { + case NO_EXPAND: + item_info->caused_expand = 0; + break; + case UNKNOWN: + item_info->caused_expand |= + (hashp->hdr.nkeys / hashp->hdr.max_bucket) > + hashp->hdr.ffactor || + item_info->pgndx > hashp->hdr.ffactor; + break; + default: + item_info->caused_expand = + num_items > hashp->hdr.ffactor ? 1 : do_expand; + break; + } + return (0); +} + +/* + * Special __addel used in big splitting; this one just puts the pointer + * to an already-allocated big page in the appropriate bucket. + */ +int32_t +#ifdef __STDC__ +add_bigptr(HTAB * hashp, ITEM_INFO * item_info, indx_t big_pgno) +#else +add_bigptr(hashp, item_info, big_pgno) + HTAB *hashp; + ITEM_INFO *item_info; + u_int32_t big_pgno; +#endif +{ + PAGE16 *pagep; + db_pgno_t next_pgno; + + pagep = __get_page(hashp, item_info->bucket, A_BUCKET); + if (!pagep) + return (-1); + + /* + * Note: in __addel(), we used item_info->pgno for the beginning of + * our search for space. Now, we use item_info->bucket, since we + * know that the space required by a big pair on the base page is + * quite small, and we may very well find that space early in the + * chain. + */ + + /* Find first page in chain that has space for a big pair. */ + while (NUM_ENT(pagep) && (NEXT_PGNO(pagep) != INVALID_PGNO)) { + if (BIGPAIRFITS(pagep)) + break; + next_pgno = NEXT_PGNO(pagep); + __put_page(hashp, pagep, A_RAW, 0); + pagep = __get_page(hashp, next_pgno, A_RAW); + if (!pagep) + return (-1); + } + if (!BIGPAIRFITS(pagep)) { + pagep = __add_ovflpage(hashp, pagep); + if (!pagep) + return (-1); +#ifdef DEBUG + assert(BIGPAIRFITS(pagep)); +#endif + } + KEY_OFF(pagep, NUM_ENT(pagep)) = BIGPAIR; + DATA_OFF(pagep, NUM_ENT(pagep)) = big_pgno; + NUM_ENT(pagep) = NUM_ENT(pagep) + 1; + + __put_page(hashp, pagep, A_RAW, 1); + + return (0); +} + +/* + * + * Returns: + * pointer on success + * NULL on error + */ +extern PAGE16 * +__add_ovflpage(hashp, pagep) + HTAB *hashp; + PAGE16 *pagep; +{ + PAGE16 *new_pagep; + u_int16_t ovfl_num; + + /* Check if we are dynamically determining the fill factor. */ + if (hashp->hdr.ffactor == DEF_FFACTOR) { + hashp->hdr.ffactor = NUM_ENT(pagep) >> 1; + if (hashp->hdr.ffactor < MIN_FFACTOR) + hashp->hdr.ffactor = MIN_FFACTOR; + } + ovfl_num = overflow_page(hashp); + + if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0) + return (NULL); + + if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL))) + return (NULL); + + NEXT_PGNO(pagep) = (db_pgno_t)OADDR_TO_PAGE(ovfl_num); + TYPE(new_pagep) = HASH_OVFLPAGE; + + __put_page(hashp, pagep, A_RAW, 1); + +#ifdef HASH_STATISTICS + hash_overflows++; +#endif + return (new_pagep); +} + +/* + * + * Returns: + * pointer on success + * NULL on error + */ +extern PAGE16 * +#ifdef __STDC__ +__add_bigpage(HTAB * hashp, PAGE16 * pagep, indx_t ndx, const u_int8_t + is_basepage) +#else +__add_bigpage(hashp, pagep, ndx, is_basepage) + HTAB *hashp; + PAGE16 *pagep; + u_int32_t ndx; + const u_int32_t is_basepage; +#endif +{ + PAGE16 *new_pagep; + u_int16_t ovfl_num; + + ovfl_num = overflow_page(hashp); + + if (__new_page(hashp, (u_int32_t)ovfl_num, A_OVFL) != 0) + return (NULL); + + if (!ovfl_num || !(new_pagep = __get_page(hashp, ovfl_num, A_OVFL))) + return (NULL); + + if (is_basepage) { + KEY_OFF(pagep, ndx) = BIGPAIR; + DATA_OFF(pagep, ndx) = (indx_t)ovfl_num; + } else + NEXT_PGNO(pagep) = ADDR(new_pagep); + + __put_page(hashp, pagep, A_RAW, 1); + + TYPE(new_pagep) = HASH_BIGPAGE; + +#ifdef HASH_STATISTICS + hash_bigpages++; +#endif + return (new_pagep); +} + +static void +#ifdef __STDC__ +page_init(HTAB * hashp, PAGE16 * pagep, db_pgno_t pgno, u_int8_t type) +#else +page_init(hashp, pagep, pgno, type) + HTAB *hashp; + PAGE16 *pagep; + db_pgno_t pgno; + u_int32_t type; +#endif +{ + NUM_ENT(pagep) = 0; + PREV_PGNO(pagep) = NEXT_PGNO(pagep) = INVALID_PGNO; + TYPE(pagep) = type; + OFFSET(pagep) = hashp->hdr.bsize - 1; + /* + * Note: since in the current version ADDR(pagep) == PREV_PGNO(pagep), + * make sure that ADDR(pagep) is set after resetting PREV_PGNO(pagep). + * We reset PREV_PGNO(pagep) just in case the macros are changed. + */ + ADDR(pagep) = pgno; + + return; +} + +int32_t +__new_page(hashp, addr, addr_type) + HTAB *hashp; + u_int32_t addr; + int32_t addr_type; +{ + db_pgno_t paddr; + PAGE16 *pagep; + + switch (addr_type) { /* Convert page number. */ + case A_BUCKET: + paddr = BUCKET_TO_PAGE(addr); + break; + case A_OVFL: + case A_BITMAP: + paddr = OADDR_TO_PAGE(addr); + break; + default: + paddr = addr; + break; + } + pagep = mpool_new(hashp->mp, &paddr, MPOOL_PAGE_REQUEST); + if (!pagep) + return (-1); +#if DEBUG_SLOW + account_page(hashp, paddr, 1); +#endif + + if (addr_type != A_BITMAP) + page_init(hashp, pagep, paddr, HASH_PAGE); + + __put_page(hashp, pagep, addr_type, 1); + + return (0); +} + +int32_t +__delete_page(hashp, pagep, page_type) + HTAB *hashp; + PAGE16 *pagep; + int32_t page_type; +{ + if (page_type == A_OVFL) + __free_ovflpage(hashp, pagep); + return (mpool_delete(hashp->mp, pagep)); +} + +u_int8_t +is_bitmap_pgno(hashp, pgno) + HTAB *hashp; + db_pgno_t pgno; +{ + int32_t i; + + for (i = 0; i < hashp->nmaps; i++) + if (OADDR_TO_PAGE(hashp->hdr.bitmaps[i]) == pgno) + return (1); + return (0); +} + +void +__pgin_routine(pg_cookie, pgno, page) + void *pg_cookie; + db_pgno_t pgno; + void *page; +{ + HTAB *hashp; + PAGE16 *pagep; + int32_t max, i; + + pagep = (PAGE16 *)page; + hashp = (HTAB *)pg_cookie; + + /* + * There are the following cases for swapping: + * 0) New page that may be unitialized. + * 1) Bucket page or overflow page. Either swap + * the header or initialize the page. + * 2) Bitmap page. Swap the whole page! + * 3) Header pages. Not handled here; these are written directly + * to the file. + */ + + if (NUM_ENT(pagep) == 0 && NEXT_PGNO(pagep) == 0 && + !is_bitmap_pgno(hashp, pgno)) { + /* XXX check for !0 LSN */ + page_init(hashp, pagep, pgno, HASH_PAGE); + return; + } + + if (hashp->hdr.lorder == DB_BYTE_ORDER) + return; + if (is_bitmap_pgno(hashp, pgno)) { + max = hashp->hdr.bsize >> 2; /* divide by 4 bytes */ + for (i = 0; i < max; i++) + M_32_SWAP(((int32_t *)pagep)[i]); + } else + swap_page_header_in(pagep); +} + +void +__pgout_routine(pg_cookie, pgno, page) + void *pg_cookie; + db_pgno_t pgno; + void *page; +{ + HTAB *hashp; + PAGE16 *pagep; + int32_t i, max; + + pagep = (PAGE16 *)page; + hashp = (HTAB *)pg_cookie; + + /* + * There are the following cases for swapping: + * 1) Bucket page or overflow page. Just swap the header. + * 2) Bitmap page. Swap the whole page! + * 3) Header pages. Not handled here; these are written directly + * to the file. + */ + + if (hashp->hdr.lorder == DB_BYTE_ORDER) + return; + if (is_bitmap_pgno(hashp, pgno)) { + max = hashp->hdr.bsize >> 2; /* divide by 4 bytes */ + for (i = 0; i < max; i++) + M_32_SWAP(((int32_t *)pagep)[i]); + } else + swap_page_header_out(pagep); +} + +/* + * + * Returns: + * 0 ==> OK + * -1 ==>failure + */ +extern int32_t +__put_page(hashp, pagep, addr_type, is_dirty) + HTAB *hashp; + PAGE16 *pagep; + int32_t addr_type, is_dirty; +{ +#if DEBUG_SLOW + account_page(hashp, + ((BKT *)((char *)pagep - sizeof(BKT)))->pgno, -1); +#endif + + return (mpool_put(hashp->mp, pagep, (is_dirty ? MPOOL_DIRTY : 0))); +} + +/* + * Returns: + * 0 indicates SUCCESS + * -1 indicates FAILURE + */ +extern PAGE16 * +__get_page(hashp, addr, addr_type) + HTAB *hashp; + u_int32_t addr; + int32_t addr_type; +{ + PAGE16 *pagep; + db_pgno_t paddr; + + switch (addr_type) { /* Convert page number. */ + case A_BUCKET: + paddr = BUCKET_TO_PAGE(addr); + break; + case A_OVFL: + case A_BITMAP: + paddr = OADDR_TO_PAGE(addr); + break; + default: + paddr = addr; + break; + } + pagep = (PAGE16 *)mpool_get(hashp->mp, paddr, 0); + +#if DEBUG_SLOW + account_page(hashp, paddr, 1); +#endif +#ifdef DEBUG + assert(ADDR(pagep) == paddr || ADDR(pagep) == 0 || + addr_type == A_BITMAP || addr_type == A_HEADER); +#endif + + return (pagep); +} + +void +swap_page_header_in(pagep) + PAGE16 *pagep; +{ + u_int32_t i; + + /* can leave type and filler alone, since they're 1-byte quantities */ + + M_32_SWAP(PREV_PGNO(pagep)); + M_32_SWAP(NEXT_PGNO(pagep)); + M_16_SWAP(NUM_ENT(pagep)); + M_16_SWAP(OFFSET(pagep)); + + for (i = 0; i < NUM_ENT(pagep); i++) { + M_16_SWAP(KEY_OFF(pagep, i)); + M_16_SWAP(DATA_OFF(pagep, i)); + } +} + +void +swap_page_header_out(pagep) + PAGE16 *pagep; +{ + u_int32_t i; + + for (i = 0; i < NUM_ENT(pagep); i++) { + M_16_SWAP(KEY_OFF(pagep, i)); + M_16_SWAP(DATA_OFF(pagep, i)) + } + + /* can leave type and filler alone, since they're 1-byte quantities */ + + M_32_SWAP(PREV_PGNO(pagep)); + M_32_SWAP(NEXT_PGNO(pagep)); + M_16_SWAP(NUM_ENT(pagep)); + M_16_SWAP(OFFSET(pagep)); +} + +#define BYTE_MASK ((1 << INT32_T_BYTE_SHIFT) -1) +/* + * Initialize a new bitmap page. Bitmap pages are left in memory + * once they are read in. + */ +extern int32_t +__ibitmap(hashp, pnum, nbits, ndx) + HTAB *hashp; + int32_t pnum, nbits, ndx; +{ + u_int32_t *ip; + int32_t clearbytes, clearints; + + /* make a new bitmap page */ + if (__new_page(hashp, pnum, A_BITMAP) != 0) + return (1); + if (!(ip = (u_int32_t *)__get_page(hashp, pnum, A_BITMAP))) + return (1); + hashp->nmaps++; + clearints = ((nbits - 1) >> INT32_T_BYTE_SHIFT) + 1; + clearbytes = clearints << INT32_T_TO_BYTE; + (void)memset((int8_t *)ip, 0, clearbytes); + (void)memset((int8_t *)ip + clearbytes, + 0xFF, hashp->hdr.bsize - clearbytes); + ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); + SETBIT(ip, 0); + hashp->hdr.bitmaps[ndx] = (u_int16_t)pnum; + hashp->mapp[ndx] = ip; + return (0); +} + +static u_int32_t +first_free(map) + u_int32_t map; +{ + u_int32_t i, mask; + + for (mask = 0x1, i = 0; i < BITS_PER_MAP; i++) { + if (!(mask & map)) + return (i); + mask = mask << 1; + } + return (i); +} + +static u_int16_t +overflow_page(hashp) + HTAB *hashp; +{ + u_int32_t *freep; + int32_t bit, first_page, free_bit, free_page, i, in_use_bits, j; + int32_t max_free, offset, splitnum; + u_int16_t addr; +#ifdef DEBUG2 + int32_t tmp1, tmp2; +#endif + + splitnum = hashp->hdr.ovfl_point; + max_free = hashp->hdr.spares[splitnum]; + + free_page = (max_free - 1) >> (hashp->hdr.bshift + BYTE_SHIFT); + free_bit = (max_free - 1) & ((hashp->hdr.bsize << BYTE_SHIFT) - 1); + + /* + * Look through all the free maps to find the first free block. + * The compiler under -Wall will complain that freep may be used + * before being set, however, this loop will ALWAYS get executed + * at least once, so freep is guaranteed to be set. + */ + first_page = hashp->hdr.last_freed >> (hashp->hdr.bshift + BYTE_SHIFT); + for (i = first_page; i <= free_page; i++) { + if (!(freep = fetch_bitmap(hashp, i))) + return (0); + if (i == free_page) + in_use_bits = free_bit; + else + in_use_bits = (hashp->hdr.bsize << BYTE_SHIFT) - 1; + + if (i == first_page) { + bit = hashp->hdr.last_freed & + ((hashp->hdr.bsize << BYTE_SHIFT) - 1); + j = bit / BITS_PER_MAP; + bit = bit & ~(BITS_PER_MAP - 1); + } else { + bit = 0; + j = 0; + } + for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) + if (freep[j] != ALL_SET) + goto found; + } + + /* No Free Page Found */ + hashp->hdr.last_freed = hashp->hdr.spares[splitnum]; + hashp->hdr.spares[splitnum]++; + offset = hashp->hdr.spares[splitnum] - + (splitnum ? hashp->hdr.spares[splitnum - 1] : 0); + +#define OVMSG "HASH: Out of overflow pages. Increase page size\n" + + if (offset > SPLITMASK) { + if (++splitnum >= NCACHED) { + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); + return (0); + } + hashp->hdr.ovfl_point = splitnum; + hashp->hdr.spares[splitnum] = hashp->hdr.spares[splitnum - 1]; + hashp->hdr.spares[splitnum - 1]--; + offset = 1; + } + /* Check if we need to allocate a new bitmap page. */ + if (free_bit == (hashp->hdr.bsize << BYTE_SHIFT) - 1) { + free_page++; + if (free_page >= NCACHED) { + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); + return (0); + } + /* + * This is tricky. The 1 indicates that you want the new page + * allocated with 1 clear bit. Actually, you are going to + * allocate 2 pages from this map. The first is going to be + * the map page, the second is the overflow page we were + * looking for. The __ibitmap routine automatically, sets + * the first bit of itself to indicate that the bitmap itself + * is in use. We would explicitly set the second bit, but + * don't have to if we tell __ibitmap not to leave it clear + * in the first place. + */ + if (__ibitmap(hashp, + (int32_t)OADDR_OF(splitnum, offset), 1, free_page)) + return (0); + hashp->hdr.spares[splitnum]++; +#ifdef DEBUG2 + free_bit = 2; +#endif + offset++; + if (offset > SPLITMASK) { + if (++splitnum >= NCACHED) { + (void)write(STDERR_FILENO, + OVMSG, sizeof(OVMSG) - 1); + return (0); + } + hashp->hdr.ovfl_point = splitnum; + hashp->hdr.spares[splitnum] = + hashp->hdr.spares[splitnum - 1]; + hashp->hdr.spares[splitnum - 1]--; + offset = 0; + } + } else { + /* + * Free_bit addresses the last used bit. Bump it to address + * the first available bit. + */ + free_bit++; + SETBIT(freep, free_bit); + } + + /* Calculate address of the new overflow page */ + addr = OADDR_OF(splitnum, offset); +#ifdef DEBUG2 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", + addr, free_bit, free_page); +#endif + + if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) { + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); + return (0); + } + return (addr); + +found: + bit = bit + first_free(freep[j]); + SETBIT(freep, bit); +#ifdef DEBUG2 + tmp1 = bit; + tmp2 = i; +#endif + /* + * Bits are addressed starting with 0, but overflow pages are addressed + * beginning at 1. Bit is a bit address number, so we need to increment + * it to convert it to a page number. + */ + bit = 1 + bit + (i * (hashp->hdr.bsize << BYTE_SHIFT)); + if (bit >= hashp->hdr.last_freed) + hashp->hdr.last_freed = bit - 1; + + /* Calculate the split number for this page */ + for (i = 0; i < splitnum && (bit > hashp->hdr.spares[i]); i++); + offset = (i ? bit - hashp->hdr.spares[i - 1] : bit); + if (offset >= SPLITMASK) + return (0); /* Out of overflow pages */ + addr = OADDR_OF(i, offset); +#ifdef DEBUG2 + (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", + addr, tmp1, tmp2); +#endif + + if (OADDR_TO_PAGE(addr) > MAX_PAGES(hashp)) { + (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); + return (0); + } + /* Allocate and return the overflow page */ + return (addr); +} + +#ifdef DEBUG +int +bucket_to_page(hashp, n) + HTAB *hashp; + int n; +{ + int ret_val; + + ret_val = n + hashp->hdr.hdrpages; + if (n != 0) + ret_val += hashp->hdr.spares[__log2(n + 1) - 1]; + return (ret_val); +} + +int32_t +oaddr_to_page(hashp, n) + HTAB *hashp; + int n; +{ + int ret_val, temp; + + temp = (1 << SPLITNUM(n)) - 1; + ret_val = bucket_to_page(hashp, temp); + ret_val += (n & SPLITMASK); + + return (ret_val); +} +#endif /* DEBUG */ + +indx_t +page_to_oaddr(hashp, pgno) + HTAB *hashp; + db_pgno_t pgno; +{ + int32_t sp, ret_val; + + /* + * To convert page number to overflow address: + * + * 1. Find a starting split point -- use 0 since there are only + * 32 split points. + * 2. Find the split point s.t. 2^sp + hdr.spares[sp] < pgno and + * 2^(sp+1) = hdr.spares[sp+1] > pgno. The overflow address will + * be located at sp. + * 3. return... + */ + pgno -= hashp->hdr.hdrpages; + for (sp = 0; sp < NCACHED; sp++) + if (POW2(sp) + hashp->hdr.spares[sp] < pgno && + (POW2(sp + 1) + hashp->hdr.spares[sp + 1]) > pgno) + break; + + ret_val = OADDR_OF(sp + 1, + pgno - ((POW2(sp + 1) - 1) + hashp->hdr.spares[sp])); +#ifdef DEBUG + assert(OADDR_TO_PAGE(ret_val) == (pgno + hashp->hdr.hdrpages)); +#endif + return (ret_val); +} + +/* + * Mark this overflow page as free. + */ +extern void +__free_ovflpage(hashp, pagep) + HTAB *hashp; + PAGE16 *pagep; +{ + u_int32_t *freep; + int32_t bit_address, free_page, free_bit; + u_int16_t addr, ndx; + + addr = page_to_oaddr(hashp, ADDR(pagep)); + +#ifdef DEBUG2 + (void)fprintf(stderr, "Freeing %d\n", addr); +#endif + ndx = ((u_int16_t)addr) >> SPLITSHIFT; + bit_address = + (ndx ? hashp->hdr.spares[ndx - 1] : 0) + (addr & SPLITMASK) - 1; + if (bit_address < hashp->hdr.last_freed) + hashp->hdr.last_freed = bit_address; + free_page = (bit_address >> (hashp->hdr.bshift + BYTE_SHIFT)); + free_bit = bit_address & ((hashp->hdr.bsize << BYTE_SHIFT) - 1); + + freep = fetch_bitmap(hashp, free_page); +#ifdef DEBUG + /* + * This had better never happen. It means we tried to read a bitmap + * that has already had overflow pages allocated off it, and we + * failed to read it from the file. + */ + if (!freep) + assert(0); +#endif + CLRBIT(freep, free_bit); +#ifdef DEBUG2 + (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", + obufp->addr, free_bit, free_page); +#endif +} + +static u_int32_t * +fetch_bitmap(hashp, ndx) + HTAB *hashp; + int32_t ndx; +{ + if (ndx >= hashp->nmaps) + return (NULL); + if (!hashp->mapp[ndx]) + hashp->mapp[ndx] = (u_int32_t *)__get_page(hashp, + hashp->hdr.bitmaps[ndx], A_BITMAP); + + return (hashp->mapp[ndx]); +} + +#ifdef DEBUG_SLOW +static void +account_page(hashp, pgno, inout) + HTAB *hashp; + db_pgno_t pgno; + int inout; +{ + static struct { + db_pgno_t pgno; + int times; + } list[100]; + static int last; + int i, j; + + if (inout == -1) /* XXX: Kluge */ + inout = 0; + + /* Find page in list. */ + for (i = 0; i < last; i++) + if (list[i].pgno == pgno) + break; + /* Not found. */ + if (i == last) { + list[last].times = inout; + list[last].pgno = pgno; + last++; + } + list[i].times = inout; + if (list[i].times == 0) { + for (j = i; j < last; j++) + list[j] = list[j + 1]; + last--; + } + for (i = 0; i < last; i++, list[i].times++) + if (list[i].times > 20 && !is_bitmap_pgno(hashp, list[i].pgno)) + (void)fprintf(stderr, + "Warning: pg %d has been out for %d times\n", + list[i].pgno, list[i].times); +} +#endif /* DEBUG_SLOW */ diff --git a/src/util/db2/hash/hsearch.c b/src/util/db2/hash/hsearch.c new file mode 100644 index 000000000..f257cd6ea --- /dev/null +++ b/src/util/db2/hash/hsearch.c @@ -0,0 +1,107 @@ +/*- + * 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. + * + * 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) +static char sccsid[] = "@(#)hsearch.c 8.5 (Berkeley) 9/21/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> + +#include <fcntl.h> +#include <string.h> + +#include "db-int.h" +#include "search.h" + +static DB *dbp = NULL; +static ENTRY retval; + +extern int +hcreate(nel) + u_int nel; +{ + HASHINFO info; + + info.nelem = nel; + info.bsize = 256; + info.ffactor = 8; + info.cachesize = 0; + info.hash = NULL; + info.lorder = 0; + dbp = (DB *)__hash_open(NULL, O_CREAT | O_RDWR, 0600, &info, 0); + return (dbp != NULL); +} + +extern ENTRY * +hsearch(item, action) + ENTRY item; + ACTION action; +{ + DBT key, val; + int status; + + if (!dbp) + return (NULL); + key.data = (u_char *)item.key; + key.size = strlen(item.key) + 1; + + if (action == ENTER) { + val.data = (u_char *)item.data; + val.size = strlen(item.data) + 1; + status = (dbp->put)(dbp, &key, &val, R_NOOVERWRITE); + if (status) + return (NULL); + } else { + /* FIND */ + status = (dbp->get)(dbp, &key, &val, 0); + if (status) + return (NULL); + else + item.data = (char *)val.data; + } + retval.key = item.key; + retval.data = item.data; + return (&retval); +} + +extern void +hdestroy() +{ + if (dbp) { + (void)(dbp->close)(dbp); + dbp = NULL; + } +} diff --git a/src/util/db2/hash/page.h b/src/util/db2/hash/page.h new file mode 100644 index 000000000..8ef8a2e29 --- /dev/null +++ b/src/util/db2/hash/page.h @@ -0,0 +1,178 @@ +/*- + * 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. + * + * @(#)page.h 8.4 (Berkeley) 11/7/95 + */ + +#define HI_MASK 0xFFFF0000 +#define LO_MASK (~HI_MASK) + +#define HI(N) ((u_int16_t)(((N) & HI_MASK) >> 16)) +#define LO(N) ((u_int16_t)((N) & LO_MASK)) + +/* Constants for big key page overhead information. */ +#define NUMSHORTS 0 +#define KEYLEN 1 +#define DATALEN 2 +#define NEXTPAGE 3 + +/* + * Hash pages store meta-data beginning at the top of the page (offset 0) + * and key/data values beginning at the bottom of the page (offset pagesize). + * Fields are always accessed via macros so that we can change the page + * format without too much pain. The only changes that will require massive + * code changes are if we no longer store key/data offsets next to each + * other (since we use that fact to compute key lengths). In the accessor + * macros below, P means a pointer to the page, I means an index of the + * particular entry being accessed. + * + * Hash base page format + * BYTE ITEM NBYTES TYPE ACCESSOR MACRO + * ---- ------------------ ------ -------- -------------- + * 0 previous page number 4 db_pgno_t PREV_PGNO(P) + * 4 next page number 4 db_pgno_t NEXT_PGNO(P) + * 8 # pairs on page 2 indx_t NUM_ENT(P) + * 10 page type 1 u_int8_t TYPE(P) + * 11 padding 1 u_int8_t none + * 12 highest free byte 2 indx_t OFFSET(P) + * 14 key offset 0 2 indx_t KEY_OFF(P, I) + * 16 data offset 0 2 indx_t DATA_OFF(P, I) + * 18 key offset 1 2 indx_t KEY_OFF(P, I) + * 20 data offset 1 2 indx_t DATA_OFF(P, I) + * ...etc... + */ + +/* Indices (in bytes) of the beginning of each of these entries */ +#define I_PREV_PGNO 0 +#define I_NEXT_PGNO 4 +#define I_ENTRIES 8 +#define I_TYPE 10 +#define I_HF_OFFSET 12 + +/* Overhead is everything prior to the first key/data pair. */ +#define PAGE_OVERHEAD (I_HF_OFFSET + sizeof(indx_t)) + +/* To allocate a pair, we need room for one key offset and one data offset. */ +#define PAIR_OVERHEAD ((sizeof(indx_t) << 1)) + +/* Use this macro to extract a value of type T from page P at offset O. */ +#define REFERENCE(P, T, O) (((T *)((u_int8_t *)(P) + O))[0]) + +/* + * Use these macros to access fields on a page; P is a PAGE16 *. + */ +#define NUM_ENT(P) (REFERENCE((P), indx_t, I_ENTRIES)) +#define PREV_PGNO(P) (REFERENCE((P), db_pgno_t, I_PREV_PGNO)) +#define NEXT_PGNO(P) (REFERENCE((P), db_pgno_t, I_NEXT_PGNO)) +#define TYPE(P) (REFERENCE((P), u_int8_t, I_TYPE)) +#define OFFSET(P) (REFERENCE((P), indx_t, I_HF_OFFSET)) +/* + * We need to store a page's own address on each page (unlike the Btree + * access method which needs the previous page). We use the PREV_PGNO + * field to store our own page number. + */ +#define ADDR(P) (PREV_PGNO((P))) + +/* Extract key/data offsets and data for a given index. */ +#define DATA_OFF(P, N) \ + REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD + sizeof(indx_t)) +#define KEY_OFF(P, N) \ + REFERENCE(P, indx_t, PAGE_OVERHEAD + N * PAIR_OVERHEAD) + +#define KEY(P, N) (((PAGE8 *)(P)) + KEY_OFF((P), (N))) +#define DATA(P, N) (((PAGE8 *)(P)) + DATA_OFF((P), (N))) + +/* + * Macros used to compute various sizes on a page. + */ +#define PAIRSIZE(K, D) (PAIR_OVERHEAD + (K)->size + (D)->size) +#define BIGOVERHEAD (4 * sizeof(u_int16_t)) +#define KEYSIZE(K) (4 * sizeof(u_int16_t) + (K)->size); +#define OVFLSIZE (2 * sizeof(u_int16_t)) +#define BIGPAGEOVERHEAD (4 * sizeof(u_int16_t)) +#define BIGPAGEOFFSET 4 +#define BIGPAGESIZE(P) ((P)->BSIZE - BIGPAGEOVERHEAD) + +#define PAGE_META(N) (((N) + 3) * sizeof(u_int16_t)) +#define MINFILL 0.75 +#define ISBIG(N, P) (((N) > ((P)->hdr.bsize * MINFILL)) ? 1 : 0) + +#define ITEMSIZE(I) (sizeof(u_int16_t) + (I)->size) + +/* + * Big key/data pages use a different page format. They have a single + * key/data "pair" containing the length of the key and data instead + * of offsets. + */ +#define BIGKEYLEN(P) (KEY_OFF((P), 0)) +#define BIGDATALEN(P) (DATA_OFF((P), 0)) +#define BIGKEY(P) (((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD) +#define BIGDATA(P) \ + (((PAGE8 *)(P)) + PAGE_OVERHEAD + PAIR_OVERHEAD + KEY_OFF((P), 0)) + + +#define OVFLPAGE 0 +#define BIGPAIR 0 +#define INVALID_PGNO 0xFFFFFFFF + +typedef unsigned short PAGE16; +typedef unsigned char PAGE8; + +#define A_BUCKET 0 +#define A_OVFL 1 +#define A_BITMAP 2 +#define A_RAW 4 +#define A_HEADER 5 + +#define PAIRFITS(P,K,D) ((PAIRSIZE((K),(D))) <= FREESPACE((P))) +#define BIGPAIRFITS(P) ((FREESPACE((P)) >= PAIR_OVERHEAD)) +/* + * Since these are all unsigned, we need to guarantee that we never go + * negative. Offset values are 0-based and overheads are one based (i.e. + * one byte of overhead is 1, not 0), so we need to convert OFFSETs to + * 1-based counting before subtraction. + */ +#define FREESPACE(P) \ + ((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD))) + +/* + * Overhead on header pages is just one word -- the length of the + * header info stored on that page. + */ +#define HEADER_OVERHEAD 4 + +#define HASH_PAGE 2 +#define HASH_BIGPAGE 3 +#define HASH_OVFLPAGE 4 diff --git a/src/util/db2/hash/page.h.patch b/src/util/db2/hash/page.h.patch new file mode 100644 index 000000000..4a0311fea --- /dev/null +++ b/src/util/db2/hash/page.h.patch @@ -0,0 +1,42 @@ +*** /tmp/,RCSt1a21720 Wed Apr 3 11:49:55 1996 +--- page.h Wed Apr 3 08:42:25 1996 +*************** +*** 158,163 + + #define PAIRFITS(P,K,D) ((PAIRSIZE((K),(D))) <= FREESPACE((P))) + #define BIGPAIRFITS(P) ((FREESPACE((P)) >= PAIR_OVERHEAD)) + #define FREESPACE(P) \ + ((OFFSET((P)) - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD))) + + +--- 158,169 ----- + + #define PAIRFITS(P,K,D) ((PAIRSIZE((K),(D))) <= FREESPACE((P))) + #define BIGPAIRFITS(P) ((FREESPACE((P)) >= PAIR_OVERHEAD)) ++ /* ++ * Since these are all unsigned, we need to guarantee that we never go ++ * negative. Offset values are 0-based and overheads are one based (i.e. ++ * one byte of overhead is 1, not 0), so we need to convert OFFSETs to ++ * 1-based counting before subtraction. ++ */ + #define FREESPACE(P) \ + ((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD))) + +*************** +*** 159,165 + #define PAIRFITS(P,K,D) ((PAIRSIZE((K),(D))) <= FREESPACE((P))) + #define BIGPAIRFITS(P) ((FREESPACE((P)) >= PAIR_OVERHEAD)) + #define FREESPACE(P) \ +! ((OFFSET((P)) - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD))) + + /* + * Overhead on header pages is just one word -- the length of the + +--- 165,171 ----- + * 1-based counting before subtraction. + */ + #define FREESPACE(P) \ +! ((OFFSET((P)) + 1 - PAGE_OVERHEAD - (NUM_ENT((P)) * PAIR_OVERHEAD))) + + /* + * Overhead on header pages is just one word -- the length of the diff --git a/src/util/db2/hash/search.h b/src/util/db2/hash/search.h new file mode 100644 index 000000000..4d3b9143e --- /dev/null +++ b/src/util/db2/hash/search.h @@ -0,0 +1,51 @@ +/*- + * 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. + * + * 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. + * + * @(#)search.h 8.1 (Berkeley) 6/4/93 + */ + +/* Backward compatibility to hsearch interface. */ +typedef struct entry { + char *key; + char *data; +} ENTRY; + +typedef enum { + FIND, ENTER +} ACTION; + +int hcreate __P((unsigned int)); +void hdestroy __P((void)); +ENTRY *hsearch __P((ENTRY, ACTION)); |