diff options
Diffstat (limited to 'src/util/db2/hash')
| -rw-r--r-- | src/util/db2/hash/Makefile.in | 13 | ||||
| -rw-r--r-- | src/util/db2/hash/Makefile.inc | 6 | ||||
| -rw-r--r-- | src/util/db2/hash/dbm.c | 356 | ||||
| -rw-r--r-- | src/util/db2/hash/extern.h | 109 | ||||
| -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 | 105 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_func.c | 201 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_log2.c | 55 | ||||
| -rw-r--r-- | src/util/db2/hash/hash_page.c | 1387 | ||||
| -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 | 55 |
16 files changed, 0 insertions, 4470 deletions
diff --git a/src/util/db2/hash/Makefile.in b/src/util/db2/hash/Makefile.in deleted file mode 100644 index e8cbe63bd..000000000 --- a/src/util/db2/hash/Makefile.in +++ /dev/null @@ -1,13 +0,0 @@ -thisconfigdir=./.. -myfulldir=util/db2/hash -mydir=hash -BUILDTOP=$(REL)..$(S)..$(S).. -STLIBOBJS= hash.o hash_bigkey.o hash_debug.o hash_func.o hash_log2.o \ - hash_page.o hsearch.o dbm.o - -LOCALINCLUDES= -I. -I$(srcdir)/../include -I../include -I$(srcdir)/../mpool \ - -I$(srcdir)/../db - -all-unix:: all-libobjs -clean-unix:: clean-libobjs -# @libobj_frag@ diff --git a/src/util/db2/hash/Makefile.inc b/src/util/db2/hash/Makefile.inc deleted file mode 100644 index 87746f721..000000000 --- a/src/util/db2/hash/Makefile.inc +++ /dev/null @@ -1,6 +0,0 @@ -# @(#)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 deleted file mode 100644 index 58c9df738..000000000 --- a/src/util/db2/hash/dbm.c +++ /dev/null @@ -1,356 +0,0 @@ -/*- - * 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 "db-dbm.h" -#include "hash.h" - -/* If the two size fields of datum and DBMT are not equal, then - * casting between structures will result in stack garbage being - * transfered. Has been observed for DEC Alpha OSF, but will handle - * the general case. - */ - -#define NEED_COPY - -/* - * - * 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 -kdb2_dbminit(file) - char *file; -{ - if (__cur_db != NULL) - (void)kdb2_dbm_close(__cur_db); - if ((__cur_db = kdb2_dbm_open(file, O_RDWR|O_BINARY, 0)) != NULL) - return (0); - if ((__cur_db = kdb2_dbm_open(file, O_RDONLY|O_BINARY, 0)) != NULL) - return (0); - return (-1); -} - -datum -kdb2_fetch(key) - datum key; -{ - datum item; - - if (__cur_db == NULL) { - no_open_db(); - item.dptr = 0; - return (item); - } - return (kdb2_dbm_fetch(__cur_db, key)); -} - -datum -kdb2_firstkey() -{ - datum item; - - if (__cur_db == NULL) { - no_open_db(); - item.dptr = 0; - return (item); - } - return (kdb2_dbm_firstkey(__cur_db)); -} - -datum -kdb2_nextkey(key) - datum key; -{ - datum item; - - if (__cur_db == NULL) { - no_open_db(); - item.dptr = 0; - return (item); - } - return (kdb2_dbm_nextkey(__cur_db)); -} - -int -kdb2_delete(key) - datum key; -{ - if (__cur_db == NULL) { - no_open_db(); - return (-1); - } - return (kdb2_dbm_delete(__cur_db, key)); -} - -int -kdb2_store(key, dat) - datum key, dat; -{ - if (__cur_db == NULL) { - no_open_db(); - return (-1); - } - return (kdb2_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 * -kdb2_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)strncpy(path, file, sizeof(path) - 1); - path[sizeof(path) - 1] = '\0'; - (void)strncat(path, DBM_SUFFIX, sizeof(path) - 1 - strlen(path)); - return ((DBM *)__hash_open(path, flags, mode, &info, 0)); -} - -/* - * Returns: - * Nothing. - */ -void -kdb2_dbm_close(db) - DBM *db; -{ - (void)(db->close)(db); -} - -/* - * Returns: - * DATUM on success - * NULL on failure - */ -datum -kdb2_dbm_fetch(db, key) - DBM *db; - datum key; -{ - datum retval; - int status; - -#ifdef NEED_COPY - DBT k, r; - - k.data = key.dptr; - k.size = key.dsize; - status = (db->get)(db, &k, &r, 0); - retval.dptr = r.data; - retval.dsize = r.size; -#else - status = (db->get)(db, (DBT *)&key, (DBT *)&retval, 0); -#endif - if (status) { - retval.dptr = NULL; - retval.dsize = 0; - } - return (retval); -} - -/* - * Returns: - * DATUM on success - * NULL on failure - */ -datum -kdb2_dbm_firstkey(db) - DBM *db; -{ - int status; - datum retkey; - -#ifdef NEED_COPY - DBT k, r; - - status = (db->seq)(db, &k, &r, R_FIRST); - retkey.dptr = k.data; - retkey.dsize = k.size; -#else - datum retdata; - - status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST); -#endif - if (status) - retkey.dptr = NULL; - return (retkey); -} - -/* - * Returns: - * DATUM on success - * NULL on failure - */ -datum -kdb2_dbm_nextkey(db) - DBM *db; -{ - int status; - datum retkey; - -#ifdef NEED_COPY - DBT k, r; - - status = (db->seq)(db, &k, &r, R_NEXT); - retkey.dptr = k.data; - retkey.dsize = k.size; -#else - datum retdata; - - status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT); -#endif - if (status) - retkey.dptr = NULL; - return (retkey); -} - -/* - * Returns: - * 0 on success - * <0 failure - */ -int -kdb2_dbm_delete(db, key) - DBM *db; - datum key; -{ - int status; - -#ifdef NEED_COPY - DBT k; - - k.data = key.dptr; - k.size = key.dsize; - status = (db->del)(db, &k, 0); -#else - status = (db->del)(db, (DBT *)&key, 0); -#endif - if (status) - return (-1); - else - return (0); -} - -/* - * Returns: - * 0 on success - * <0 failure - * 1 if DBM_INSERT and entry exists - */ -int -kdb2_dbm_store(db, key, content, flags) - DBM *db; - datum key, content; - int flags; -{ -#ifdef NEED_COPY - DBT k, c; - - k.data = key.dptr; - k.size = key.dsize; - c.data = content.dptr; - c.size = content.dsize; - return ((db->put)(db, &k, &c, - (flags == DBM_INSERT) ? R_NOOVERWRITE : 0)); -#else - return ((db->put)(db, (DBT *)&key, (DBT *)&content, - (flags == DBM_INSERT) ? R_NOOVERWRITE : 0)); -#endif -} - -int -kdb2_dbm_error(db) - DBM *db; -{ - HTAB *hp; - - hp = (HTAB *)db->internal; - return (hp->local_errno); -} - -int -kdb2_dbm_clearerr(db) - DBM *db; -{ - HTAB *hp; - - hp = (HTAB *)db->internal; - hp->local_errno = 0; - return (0); -} - -int -kdb2_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 deleted file mode 100644 index 872b6b0fe..000000000 --- a/src/util/db2/hash/extern.h +++ /dev/null @@ -1,109 +0,0 @@ -/*- - * 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 - */ - -#define __add_bigpage __kdb2_add_bigpage -#define __add_ovflpage __kdb2_add_ovflpage -#define __addel __kdb2_addel -#define __alloc_tmp __kdb2_alloc_tmp -#define __big_delete __kdb2_big_delete -#define __big_insert __kdb2_big_insert -#define __big_keydata __kdb2_big_keydata -#define __big_return __kdb2_big_return -#define __call_hash __kdb2_call_hash -#define __cursor_creat __kdb2_cursor_creat -#define __delete_page __kdb2_delete_page -#define __delpair __kdb2_delpair -#define __expand_table __kdb2_expand_table -#define __find_bigpair __kdb2_find_bigpair -#define __free_ovflpage __kdb2_free_ovflpage -#define __get_bigkey __kdb2_get_bigkey -#define __get_buf __kdb2_get_buf -#define __get_item __kdb2_get_item -#define __get_item_done __kdb2_get_item_done -#define __get_item_first __kdb2_get_item_first -#define __get_item_next __kdb2_get_item_next -#define __get_item_reset __kdb2_get_item_reset -#define __get_page __kdb2_get_page -#define __ibitmap __kdb2_ibitmap -#define __log2 __kdb2_log2 -#define __new_page __kdb2_new_page -#define __pgin_routine __kdb2_pgin_routine -#define __pgout_routine __kdb2_pgout_routine -#define __put_buf __kdb2_put_buf -#define __put_page __kdb2_put_page -#define __reclaim_tmp __kdb2_reclaim_tmp -#define __split_page __kdb2_split_page - -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 deleted file mode 100644 index 0e254938e..000000000 --- a/src/util/db2/hash/hash.c +++ /dev/null @@ -1,1068 +0,0 @@ -/*- - * 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, const 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 *, const 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 * -__kdb2_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 = 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|O_BINARY, 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, 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; - const 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; - - /* - * 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. - */ -static 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); -} - -static 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->local_errno = errno = EINVAL; - return (ERROR); - } - return (hash_access(hashp, HASH_GET, 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->local_errno = errno = EINVAL; - return (ERROR); - } - if ((hashp->flags & O_ACCMODE) == O_RDONLY) { - hashp->local_errno = errno = EPERM; - return (ERROR); - } - return (hash_access(hashp, flag == R_NOOVERWRITE ? - HASH_PUTNEW : HASH_PUT, 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->local_errno = errno = EINVAL; - return (ERROR); - } - if ((hashp->flags & O_ACCMODE) == O_RDONLY) { - hashp->local_errno = errno = EPERM; - return (ERROR); - } - - return (hash_access(hashp, HASH_DELETE, key, NULL)); -} - -/* - * Assume that hashp has been set in wrapper routine. - */ -static int32_t -hash_access(hashp, action, key, val) - HTAB *hashp; - ACTION action; - const DBT *key; - DBT *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; -} - -static 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->local_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); -} - -static 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 deleted file mode 100644 index b72cc0d26..000000000 --- a/src/util/db2/hash/hash.c.patch +++ /dev/null @@ -1,109 +0,0 @@ -*** /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 deleted file mode 100644 index b202fc9f2..000000000 --- a/src/util/db2/hash/hash.h +++ /dev/null @@ -1,196 +0,0 @@ -/*- - * 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 */ - const 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 local_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_SHIFT 12 /* log2(BUCKET) */ -#define DEF_BUCKET_SIZE (1<<DEF_BUCKET_SHIFT) -#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ -#define DEF_SEGSIZE (1<<DEF_SEGSIZE_SHIFT) -#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 deleted file mode 100644 index 06210a57c..000000000 --- a/src/util/db2/hash/hash_bigkey.c +++ /dev/null @@ -1,483 +0,0 @@ -/*- - * 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 = (u_int8_t *)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 = (u_int8_t *)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 = (u_int8_t *)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 deleted file mode 100644 index 69229fc8d..000000000 --- a/src/util/db2/hash/hash_debug.c +++ /dev/null @@ -1,105 +0,0 @@ -/*- - * 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" - -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 deleted file mode 100644 index 1dee69460..000000000 --- a/src/util/db2/hash/hash_func.c +++ /dev/null @@ -1,201 +0,0 @@ -/*- - * 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" - -#if 0 -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)); -#endif -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 - -#if 0 -static 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)) - -static 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. - */ -static 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); -} -#endif - - -/* Chris Torek's hash function. */ -static u_int32_t -hash4(key, len) - const void *key; - size_t len; -{ - u_int32_t h, loop; - const u_int8_t *k; - -#define HASH4a h = (h << 5) - h + *k++; -#define HASH4b h = (h << 5) + h + *k++; -#define HASH4 HASH4b - - h = 0; - k = (const 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 deleted file mode 100644 index 8c710e5d2..000000000 --- a/src/util/db2/hash/hash_log2.c +++ /dev/null @@ -1,55 +0,0 @@ -/*- - * 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" -#include "hash.h" -#include "page.h" -#include "extern.h" - -u_int32_t -__kdb2_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 deleted file mode 100644 index e25115d3f..000000000 --- a/src/util/db2/hash/hash_page.c +++ /dev/null @@ -1,1387 +0,0 @@ -/*- - * 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 status; - - status = __get_item(hashp, cursorp, key, val, item_info); - cursorp->ndx++; - cursorp->pgndx++; - return (status); -} - -/* - * 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. - */ -static 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. - */ -static 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 (!ovfl_num) - return (NULL); - - 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 (!ovfl_num) - return (NULL); - - 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)); -} - -static 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); -} - -static 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)); - } -} - -static 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); -} - -/* - * returns 0 on error - */ -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 */ - -static 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 deleted file mode 100644 index 02ff7ef84..000000000 --- a/src/util/db2/hash/hsearch.c +++ /dev/null @@ -1,107 +0,0 @@ -/*- - * 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 | O_BINARY, 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 deleted file mode 100644 index 8ef8a2e29..000000000 --- a/src/util/db2/hash/page.h +++ /dev/null @@ -1,178 +0,0 @@ -/*- - * 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 deleted file mode 100644 index 4a0311fea..000000000 --- a/src/util/db2/hash/page.h.patch +++ /dev/null @@ -1,42 +0,0 @@ -*** /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 deleted file mode 100644 index 6d6a0a82f..000000000 --- a/src/util/db2/hash/search.h +++ /dev/null @@ -1,55 +0,0 @@ -/*- - * 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; - -#define hcreate kdb2_hcreate -#define hdestroy kdb2_hdestroy -#define hsearch kdb2_hsearch - -int hcreate __P((unsigned int)); -void hdestroy __P((void)); -ENTRY *hsearch __P((ENTRY, ACTION)); |