Newsgroups: comp.sources.unix From: bostic@cs.berkeley.edu (Keith Bostic) Subject: v26i281: db-1.6 - A New Hashing Package for UNIX(tm) (updates dbm/ndbm), Part02/09 Sender: unix-sources-moderator@gw.home.vix.com Approved: vixie@gw.home.vix.com Submitted-By: bostic@cs.berkeley.edu (Keith Bostic) Posting-Number: Volume 26, Issue 281 Archive-Name: db-1.6/part02 #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh 'PORT/clib/memmove.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Chris Torek. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)bcopy.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X#include X X/* X * sizeof(word) MUST BE A POWER OF TWO X * SO THAT wmask BELOW IS ALL ONES X */ Xtypedef int word; /* "word" used for optimal copy speed */ X X#define wsize sizeof(word) X#define wmask (wsize - 1) X X/* X * Copy a block of memory, handling overlap. X * This is the routine that actually implements X * (the portable versions of) bcopy, memcpy, and memmove. X */ X#ifdef MEMCOPY Xvoid * Xmemcpy(dst0, src0, length) X#else X#ifdef MEMMOVE Xvoid * Xmemmove(dst0, src0, length) X#else Xvoid Xbcopy(src0, dst0, length) X#endif X#endif X void *dst0; X const void *src0; X register size_t length; X{ X register char *dst = dst0; X register const char *src = src0; X register size_t t; X X if (length == 0 || dst == src) /* nothing to do */ X goto done; X X /* X * Macros: loop-t-times; and loop-t-times, t>0 X */ X#define TLOOP(s) if (t) TLOOP1(s) X#define TLOOP1(s) do { s; } while (--t) X X if ((unsigned long)dst < (unsigned long)src) { X /* X * Copy forward. X */ X t = (int)src; /* only need low bits */ X if ((t | (int)dst) & wmask) { X /* X * Try to align operands. This cannot be done X * unless the low bits match. X */ X if ((t ^ (int)dst) & wmask || length < wsize) X t = length; X else X t = wsize - (t & wmask); X length -= t; X TLOOP1(*dst++ = *src++); X } X /* X * Copy whole words, then mop up any trailing bytes. X */ X t = length / wsize; X TLOOP(*(word *)dst = *(word *)src; src += wsize; dst += wsize); X t = length & wmask; X TLOOP(*dst++ = *src++); X } else { X /* X * Copy backwards. Otherwise essentially the same. X * Alignment works as before, except that it takes X * (t&wmask) bytes to align, not wsize-(t&wmask). X */ X src += length; X dst += length; X t = (int)src; X if ((t | (int)dst) & wmask) { X if ((t ^ (int)dst) & wmask || length <= wsize) X t = length; X else X t &= wmask; X length -= t; X TLOOP1(*--dst = *--src); X } X t = length / wsize; X TLOOP(src -= wsize; dst -= wsize; *(word *)dst = *(word *)src); X t = length & wmask; X TLOOP(*--dst = *--src); X } Xdone: X#if defined(MEMCOPY) || defined(MEMMOVE) X return (dst0); X#else X return; X#endif X} END_OF_FILE if test 4175 -ne `wc -c <'PORT/clib/memmove.c'`; then echo shar: \"'PORT/clib/memmove.c'\" unpacked with wrong size! fi # end of 'PORT/clib/memmove.c' fi if test -f 'PORT/include/cdefs.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'PORT/include/cdefs.h'\" else echo shar: Extracting \"'PORT/include/cdefs.h'\" \(3638 characters\) sed "s/^X//" >'PORT/include/cdefs.h' <<'END_OF_FILE' X/* X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X * X * @(#)cdefs.h 8.1 (Berkeley) 6/2/93 X */ X X#ifndef _CDEFS_H_ X#define _CDEFS_H_ X X#if defined(__cplusplus) X#define __BEGIN_DECLS extern "C" { X#define __END_DECLS }; X#else X#define __BEGIN_DECLS X#define __END_DECLS X#endif X X/* X * The __CONCAT macro is used to concatenate parts of symbol names, e.g. X * with "#define OLD(foo) __CONCAT(old,foo)", OLD(foo) produces oldfoo. X * The __CONCAT macro is a bit tricky -- make sure you don't put spaces X * in between its arguments. __CONCAT can also concatenate double-quoted X * strings produced by the __STRING macro, but this only works with ANSI C. X */ X#if defined(__STDC__) || defined(__cplusplus) X#define __P(protos) protos /* full-blown ANSI C */ X#define __CONCAT(x,y) x ## y X#define __STRING(x) #x X X#else /* !(__STDC__ || __cplusplus) */ X#define __P(protos) () /* traditional C preprocessor */ X#define __CONCAT(x,y) x/**/y X#define __STRING(x) "x" X X#ifdef __GNUC__ X#define const __const /* GCC: ANSI C with -traditional */ X#define inline __inline X#define signed __signed X#define volatile __volatile X X#else /* !__GNUC__ */ X#define const /* delete ANSI C keywords */ X#define inline X#define signed X#define volatile X#endif /* !__GNUC__ */ X#endif /* !(__STDC__ || __cplusplus) */ X X/* X * GCC has extensions for declaring functions as `pure' (always returns X * the same value given the same inputs, i.e., has no external state and X * no side effects) and `dead' (nonreturning). These mainly affect X * optimization and warnings. Unfortunately, GCC complains if these are X * used under strict ANSI mode (`gcc -ansi -pedantic'), hence we need to X * define them only if compiling without this. X */ X#if defined(__GNUC__) && !defined(__STRICT_ANSI__) X#define __dead __volatile X#define __pure __const X#else X#define __dead X#define __pure X#endif X X#endif /* !_CDEFS_H_ */ END_OF_FILE if test 3638 -ne `wc -c <'PORT/include/cdefs.h'`; then echo shar: \"'PORT/include/cdefs.h'\" unpacked with wrong size! fi # end of 'PORT/include/cdefs.h' fi if test -f 'PORT/include/mpool.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'PORT/include/mpool.h'\" else echo shar: Extracting \"'PORT/include/mpool.h'\" \(5225 characters\) sed "s/^X//" >'PORT/include/mpool.h' <<'END_OF_FILE' X/*- X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X * X * @(#)mpool.h 8.1 (Berkeley) 6/2/93 X */ X X/* X * The memory pool scheme is a simple one. Each in memory page is referenced X * by a bucket which is threaded in three ways. All active pages are threaded X * on a hash chain (hashed by the page number) and an lru chain. Inactive X * pages are threaded on a free chain. Each reference to a memory pool is X * handed an MPOOL which is the opaque cookie passed to all of the memory X * routines. X */ X#define HASHSIZE 128 X#define HASHKEY(pgno) ((pgno - 1) % HASHSIZE) X X/* The BKT structures are the elements of the lists. */ Xtypedef struct BKT { X struct BKT *hnext; /* next hash bucket */ X struct BKT *hprev; /* previous hash bucket */ X struct BKT *cnext; /* next free/lru bucket */ X struct BKT *cprev; /* previous free/lru bucket */ X void *page; /* page */ X pgno_t pgno; /* page number */ X X#define MPOOL_DIRTY 0x01 /* page needs to be written */ X#define MPOOL_PINNED 0x02 /* page is pinned into memory */ X unsigned long flags; /* flags */ X} BKT; X X/* The BKTHDR structures are the heads of the lists. */ Xtypedef struct BKTHDR { X struct BKT *hnext; /* next hash bucket */ X struct BKT *hprev; /* previous hash bucket */ X struct BKT *cnext; /* next free/lru bucket */ X struct BKT *cprev; /* previous free/lru bucket */ X} BKTHDR; X Xtypedef struct MPOOL { X BKTHDR free; /* The free list. */ X BKTHDR lru; /* The LRU list. */ X BKTHDR hashtable[HASHSIZE]; /* Hashed list by page number. */ X pgno_t curcache; /* Current number of cached pages. */ X pgno_t maxcache; /* Max number of cached pages. */ X pgno_t npages; /* Number of pages in the file. */ X u_long pagesize; /* File page size. */ X int fd; /* File descriptor. */ X /* Page in conversion routine. */ X void (*pgin) __P((void *, pgno_t, void *)); X /* Page out conversion routine. */ X void (*pgout) __P((void *, pgno_t, void *)); X void *pgcookie; /* Cookie for page in/out routines. */ X#ifdef STATISTICS X unsigned long cachehit; X unsigned long cachemiss; X unsigned long pagealloc; X unsigned long pageflush; X unsigned long pageget; X unsigned long pagenew; X unsigned long pageput; X unsigned long pageread; X unsigned long pagewrite; X#endif X} MPOOL; X X#ifdef __MPOOLINTERFACE_PRIVATE X/* Macros to insert/delete into/from hash chain. */ X#define rmhash(bp) { \ X (bp)->hprev->hnext = (bp)->hnext; \ X (bp)->hnext->hprev = (bp)->hprev; \ X} X#define inshash(bp, pg) { \ X hp = &mp->hashtable[HASHKEY(pg)]; \ X (bp)->hnext = hp->hnext; \ X (bp)->hprev = (struct BKT *)hp; \ X hp->hnext->hprev = (bp); \ X hp->hnext = (bp); \ X} X X/* Macros to insert/delete into/from lru and free chains. */ X#define rmchain(bp) { \ X (bp)->cprev->cnext = (bp)->cnext; \ X (bp)->cnext->cprev = (bp)->cprev; \ X} X#define inschain(bp, dp) { \ X (bp)->cnext = (dp)->cnext; \ X (bp)->cprev = (struct BKT *)(dp); \ X (dp)->cnext->cprev = (bp); \ X (dp)->cnext = (bp); \ X} X#endif X X__BEGIN_DECLS XMPOOL *mpool_open __P((DBT *, int, pgno_t, pgno_t)); Xvoid mpool_filter __P((MPOOL *, void (*)(void *, pgno_t, void *), X void (*)(void *, pgno_t, void *), void *)); Xvoid *mpool_new __P((MPOOL *, pgno_t *)); Xvoid *mpool_get __P((MPOOL *, pgno_t, u_int)); Xint mpool_put __P((MPOOL *, void *, u_int)); Xint mpool_sync __P((MPOOL *)); Xint mpool_close __P((MPOOL *)); X#ifdef STATISTICS Xvoid mpool_stat __P((MPOOL *)); X#endif X__END_DECLS END_OF_FILE if test 5225 -ne `wc -c <'PORT/include/mpool.h'`; then echo shar: \"'PORT/include/mpool.h'\" unpacked with wrong size! fi # end of 'PORT/include/mpool.h' fi if test -f 'PORT/sys/cdefs.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'PORT/sys/cdefs.h'\" else echo shar: Extracting \"'PORT/sys/cdefs.h'\" \(3638 characters\) sed "s/^X//" >'PORT/sys/cdefs.h' <<'END_OF_FILE' X/* X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X * X * @(#)cdefs.h 8.1 (Berkeley) 6/2/93 X */ X X#ifndef _CDEFS_H_ X#define _CDEFS_H_ X X#if defined(__cplusplus) X#define __BEGIN_DECLS extern "C" { X#define __END_DECLS }; X#else X#define __BEGIN_DECLS X#define __END_DECLS X#endif X X/* X * The __CONCAT macro is used to concatenate parts of symbol names, e.g. X * with "#define OLD(foo) __CONCAT(old,foo)", OLD(foo) produces oldfoo. X * The __CONCAT macro is a bit tricky -- make sure you don't put spaces X * in between its arguments. __CONCAT can also concatenate double-quoted X * strings produced by the __STRING macro, but this only works with ANSI C. X */ X#if defined(__STDC__) || defined(__cplusplus) X#define __P(protos) protos /* full-blown ANSI C */ X#define __CONCAT(x,y) x ## y X#define __STRING(x) #x X X#else /* !(__STDC__ || __cplusplus) */ X#define __P(protos) () /* traditional C preprocessor */ X#define __CONCAT(x,y) x/**/y X#define __STRING(x) "x" X X#ifdef __GNUC__ X#define const __const /* GCC: ANSI C with -traditional */ X#define inline __inline X#define signed __signed X#define volatile __volatile X X#else /* !__GNUC__ */ X#define const /* delete ANSI C keywords */ X#define inline X#define signed X#define volatile X#endif /* !__GNUC__ */ X#endif /* !(__STDC__ || __cplusplus) */ X X/* X * GCC has extensions for declaring functions as `pure' (always returns X * the same value given the same inputs, i.e., has no external state and X * no side effects) and `dead' (nonreturning). These mainly affect X * optimization and warnings. Unfortunately, GCC complains if these are X * used under strict ANSI mode (`gcc -ansi -pedantic'), hence we need to X * define them only if compiling without this. X */ X#if defined(__GNUC__) && !defined(__STRICT_ANSI__) X#define __dead __volatile X#define __pure __const X#else X#define __dead X#define __pure X#endif X X#endif /* !_CDEFS_H_ */ END_OF_FILE if test 3638 -ne `wc -c <'PORT/sys/cdefs.h'`; then echo shar: \"'PORT/sys/cdefs.h'\" unpacked with wrong size! fi # end of 'PORT/sys/cdefs.h' fi if test -f 'PORT/sys/mpool.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'PORT/sys/mpool.h'\" else echo shar: Extracting \"'PORT/sys/mpool.h'\" \(5225 characters\) sed "s/^X//" >'PORT/sys/mpool.h' <<'END_OF_FILE' X/*- X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X * X * @(#)mpool.h 8.1 (Berkeley) 6/2/93 X */ X X/* X * The memory pool scheme is a simple one. Each in memory page is referenced X * by a bucket which is threaded in three ways. All active pages are threaded X * on a hash chain (hashed by the page number) and an lru chain. Inactive X * pages are threaded on a free chain. Each reference to a memory pool is X * handed an MPOOL which is the opaque cookie passed to all of the memory X * routines. X */ X#define HASHSIZE 128 X#define HASHKEY(pgno) ((pgno - 1) % HASHSIZE) X X/* The BKT structures are the elements of the lists. */ Xtypedef struct BKT { X struct BKT *hnext; /* next hash bucket */ X struct BKT *hprev; /* previous hash bucket */ X struct BKT *cnext; /* next free/lru bucket */ X struct BKT *cprev; /* previous free/lru bucket */ X void *page; /* page */ X pgno_t pgno; /* page number */ X X#define MPOOL_DIRTY 0x01 /* page needs to be written */ X#define MPOOL_PINNED 0x02 /* page is pinned into memory */ X unsigned long flags; /* flags */ X} BKT; X X/* The BKTHDR structures are the heads of the lists. */ Xtypedef struct BKTHDR { X struct BKT *hnext; /* next hash bucket */ X struct BKT *hprev; /* previous hash bucket */ X struct BKT *cnext; /* next free/lru bucket */ X struct BKT *cprev; /* previous free/lru bucket */ X} BKTHDR; X Xtypedef struct MPOOL { X BKTHDR free; /* The free list. */ X BKTHDR lru; /* The LRU list. */ X BKTHDR hashtable[HASHSIZE]; /* Hashed list by page number. */ X pgno_t curcache; /* Current number of cached pages. */ X pgno_t maxcache; /* Max number of cached pages. */ X pgno_t npages; /* Number of pages in the file. */ X u_long pagesize; /* File page size. */ X int fd; /* File descriptor. */ X /* Page in conversion routine. */ X void (*pgin) __P((void *, pgno_t, void *)); X /* Page out conversion routine. */ X void (*pgout) __P((void *, pgno_t, void *)); X void *pgcookie; /* Cookie for page in/out routines. */ X#ifdef STATISTICS X unsigned long cachehit; X unsigned long cachemiss; X unsigned long pagealloc; X unsigned long pageflush; X unsigned long pageget; X unsigned long pagenew; X unsigned long pageput; X unsigned long pageread; X unsigned long pagewrite; X#endif X} MPOOL; X X#ifdef __MPOOLINTERFACE_PRIVATE X/* Macros to insert/delete into/from hash chain. */ X#define rmhash(bp) { \ X (bp)->hprev->hnext = (bp)->hnext; \ X (bp)->hnext->hprev = (bp)->hprev; \ X} X#define inshash(bp, pg) { \ X hp = &mp->hashtable[HASHKEY(pg)]; \ X (bp)->hnext = hp->hnext; \ X (bp)->hprev = (struct BKT *)hp; \ X hp->hnext->hprev = (bp); \ X hp->hnext = (bp); \ X} X X/* Macros to insert/delete into/from lru and free chains. */ X#define rmchain(bp) { \ X (bp)->cprev->cnext = (bp)->cnext; \ X (bp)->cnext->cprev = (bp)->cprev; \ X} X#define inschain(bp, dp) { \ X (bp)->cnext = (dp)->cnext; \ X (bp)->cprev = (struct BKT *)(dp); \ X (dp)->cnext->cprev = (bp); \ X (dp)->cnext = (bp); \ X} X#endif X X__BEGIN_DECLS XMPOOL *mpool_open __P((DBT *, int, pgno_t, pgno_t)); Xvoid mpool_filter __P((MPOOL *, void (*)(void *, pgno_t, void *), X void (*)(void *, pgno_t, void *), void *)); Xvoid *mpool_new __P((MPOOL *, pgno_t *)); Xvoid *mpool_get __P((MPOOL *, pgno_t, u_int)); Xint mpool_put __P((MPOOL *, void *, u_int)); Xint mpool_sync __P((MPOOL *)); Xint mpool_close __P((MPOOL *)); X#ifdef STATISTICS Xvoid mpool_stat __P((MPOOL *)); X#endif X__END_DECLS END_OF_FILE if test 5225 -ne `wc -c <'PORT/sys/mpool.h'`; then echo shar: \"'PORT/sys/mpool.h'\" unpacked with wrong size! fi # end of 'PORT/sys/mpool.h' fi if test -f 'btree/bt_close.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_close.c'\" else echo shar: Extracting \"'btree/bt_close.c'\" \(4880 characters\) sed "s/^X//" >'btree/bt_close.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Mike Olson. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)bt_close.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X X#include X#include X#include X#include X#include X X#include X#include "btree.h" X Xstatic int bt_meta __P((BTREE *)); X X/* X * BT_CLOSE -- Close a btree. X * X * Parameters: X * dbp: pointer to access method X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xint X__bt_close(dbp) X DB *dbp; X{ X BTREE *t; X int fd; X X t = dbp->internal; X X /* X * Delete any already deleted record that we've been saving X * because the cursor pointed to it. X */ X if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor)) X return (RET_ERROR); X X if (__bt_sync(dbp, 0) == RET_ERROR) X return (RET_ERROR); X X if (mpool_close(t->bt_mp) == RET_ERROR) X return (RET_ERROR); X X if (t->bt_stack) X free(t->bt_stack); X if (t->bt_kbuf) X free(t->bt_kbuf); X if (t->bt_dbuf) X free(t->bt_dbuf); X X fd = t->bt_fd; X free(t); X free(dbp); X return (close(fd) ? RET_ERROR : RET_SUCCESS); X} X X/* X * BT_SYNC -- sync the btree to disk. X * X * Parameters: X * dbp: pointer to access method X * X * Returns: X * RET_SUCCESS, RET_ERROR. X */ Xint X__bt_sync(dbp, flags) X const DB *dbp; X u_int flags; X{ X BTREE *t; X int status; X PAGE *h; X void *p; X X if (flags != 0) { X errno = EINVAL; X return (RET_ERROR); X } X X t = dbp->internal; X X if (ISSET(t, B_INMEM | B_RDONLY) || !ISSET(t, B_MODIFIED)) X return (RET_SUCCESS); X X if (ISSET(t, B_METADIRTY) && bt_meta(t) == RET_ERROR) X return (RET_ERROR); X X /* X * Nastiness. If the cursor has been marked for deletion, but not X * actually deleted, we have to make a copy of the page, delete the X * key/data item, sync the file, and then restore the original page X * contents. X */ X if (ISSET(t, B_DELCRSR)) { X if ((p = malloc(t->bt_psize)) == NULL) X return (RET_ERROR); X if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL) X return (RET_ERROR); X memmove(p, h, t->bt_psize); X if ((status = X __bt_dleaf(t, h, t->bt_bcursor.index)) == RET_ERROR) X goto ecrsr; X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X } X X if ((status = mpool_sync(t->bt_mp)) == RET_SUCCESS) X CLR(t, B_MODIFIED); X Xecrsr: if (ISSET(t, B_DELCRSR)) { X if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL) X return (RET_ERROR); X memmove(h, p, t->bt_psize); X free(p); X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X } X return (status); X} X X/* X * BT_META -- write the tree meta data to disk. X * X * Parameters: X * t: tree X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xstatic int Xbt_meta(t) X BTREE *t; X{ X BTMETA m; X void *p; X X if ((p = mpool_get(t->bt_mp, P_META, 0)) == NULL) X return (RET_ERROR); X X /* Fill in metadata. */ X m.m_magic = BTREEMAGIC; X m.m_version = BTREEVERSION; X m.m_psize = t->bt_psize; X m.m_free = t->bt_free; X m.m_nrecs = t->bt_nrecs; X m.m_flags = t->bt_flags & SAVEMETA; X X memmove(p, &m, sizeof(BTMETA)); X mpool_put(t->bt_mp, p, MPOOL_DIRTY); X return (RET_SUCCESS); X} END_OF_FILE if test 4880 -ne `wc -c <'btree/bt_close.c'`; then echo shar: \"'btree/bt_close.c'\" unpacked with wrong size! fi # end of 'btree/bt_close.c' fi if test -f 'btree/bt_conv.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_conv.c'\" else echo shar: Extracting \"'btree/bt_conv.c'\" \(5253 characters\) sed "s/^X//" >'btree/bt_conv.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Mike Olson. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)bt_conv.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X X#include X X#include X#include "btree.h" X Xstatic void mswap __P((PAGE *)); X X/* X * __BT_BPGIN, __BT_BPGOUT -- X * Convert host-specific number layout to/from the host-independent X * format stored on disk. X * X * Parameters: X * t: tree X * pg: page number X * h: page to convert X */ Xvoid X__bt_pgin(t, pg, pp) X void *t; X pgno_t pg; X void *pp; X{ X PAGE *h; X int i, top; X u_char flags; X char *p; X X if (!ISSET(((BTREE *)t), B_NEEDSWAP)) X return; X if (pg == P_META) { X mswap(pp); X return; X } X X h = pp; X BLSWAP(h->pgno); X BLSWAP(h->prevpg); X BLSWAP(h->nextpg); X BLSWAP(h->flags); X BSSWAP(h->lower); X BSSWAP(h->upper); X X top = NEXTINDEX(h); X if ((h->flags & P_TYPE) == P_BINTERNAL) X for (i = 0; i < top; i++) { X BSSWAP(h->linp[i]); X p = (char *)GETBINTERNAL(h, i); X BLPSWAP(p); X p += sizeof(size_t); X BLPSWAP(p); X p += sizeof(pgno_t); X if (*(u_char *)p & P_BIGKEY) { X p += sizeof(u_char); X BLPSWAP(p); X p += sizeof(pgno_t); X BLPSWAP(p); X } X } X else if ((h->flags & P_TYPE) == P_BLEAF) X for (i = 0; i < top; i++) { X BSSWAP(h->linp[i]); X p = (char *)GETBLEAF(h, i); X BLPSWAP(p); X p += sizeof(size_t); X BLPSWAP(p); X p += sizeof(size_t); X flags = *(u_char *)p; X if (flags & (P_BIGKEY | P_BIGDATA)) { X p += sizeof(u_char); X if (flags & P_BIGKEY) { X BLPSWAP(p); X p += sizeof(pgno_t); X BLPSWAP(p); X } X if (flags & P_BIGDATA) { X p += sizeof(size_t); X BLPSWAP(p); X p += sizeof(pgno_t); X BLPSWAP(p); X } X } X } X} X Xvoid X__bt_pgout(t, pg, pp) X void *t; X pgno_t pg; X void *pp; X{ X PAGE *h; X int i, top; X u_char flags; X char *p; X X if (!ISSET(((BTREE *)t), B_NEEDSWAP)) X return; X if (pg == P_META) { X mswap(pp); X return; X } X X h = pp; X top = NEXTINDEX(h); X if ((h->flags & P_TYPE) == P_BINTERNAL) X for (i = 0; i < top; i++) { X p = (char *)GETBINTERNAL(h, i); X BLPSWAP(p); X p += sizeof(size_t); X BLPSWAP(p); X p += sizeof(pgno_t); X if (*(u_char *)p & P_BIGKEY) { X p += sizeof(u_char); X BLPSWAP(p); X p += sizeof(pgno_t); X BLPSWAP(p); X } X BSSWAP(h->linp[i]); X } X else if ((h->flags & P_TYPE) == P_BLEAF) X for (i = 0; i < top; i++) { X p = (char *)GETBLEAF(h, i); X BLPSWAP(p); X p += sizeof(size_t); X BLPSWAP(p); X p += sizeof(size_t); X flags = *(u_char *)p; X if (flags & (P_BIGKEY | P_BIGDATA)) { X p += sizeof(u_char); X if (flags & P_BIGKEY) { X BLPSWAP(p); X p += sizeof(pgno_t); X BLPSWAP(p); X } X if (flags & P_BIGDATA) { X p += sizeof(size_t); X BLPSWAP(p); X p += sizeof(pgno_t); X BLPSWAP(p); X } X } X BSSWAP(h->linp[i]); X } X X BLSWAP(h->pgno); X BLSWAP(h->prevpg); X BLSWAP(h->nextpg); X BLSWAP(h->flags); X BSSWAP(h->lower); X BSSWAP(h->upper); X} X X/* X * MSWAP -- Actually swap the bytes on the meta page. X * X * Parameters: X * p: page to convert X */ Xstatic void Xmswap(pg) X PAGE *pg; X{ X char *p; X X p = (char *)pg; X BLPSWAP(p); /* m_magic */ X p += sizeof(u_long); X BLPSWAP(p); /* m_version */ X p += sizeof(u_long); X BLPSWAP(p); /* m_psize */ X p += sizeof(u_long); X BLPSWAP(p); /* m_free */ X p += sizeof(u_long); X BLPSWAP(p); /* m_nrecs */ X p += sizeof(u_long); X BLPSWAP(p); /* m_flags */ X p += sizeof(u_long); X} END_OF_FILE if test 5253 -ne `wc -c <'btree/bt_conv.c'`; then echo shar: \"'btree/bt_conv.c'\" unpacked with wrong size! fi # end of 'btree/bt_conv.c' fi if test -f 'btree/bt_search.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_search.c'\" else echo shar: Extracting \"'btree/bt_search.c'\" \(3809 characters\) sed "s/^X//" >'btree/bt_search.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Mike Olson. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)bt_search.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X X#include X X#include X#include "btree.h" X X/* X * __BT_SEARCH -- Search a btree for a key. X * X * Parameters: X * t: tree to search X * key: key to find X * exactp: pointer to exact match flag X * X * Returns: X * EPG for matching record, if any, or the EPG for the location of the X * key, if it were inserted into the tree. X * X * Warnings: X * The EPG returned is in static memory, and will be overwritten by the X * next search of any kind in any tree. X */ XEPG * X__bt_search(t, key, exactp) X BTREE *t; X const DBT *key; X int *exactp; X{ X register indx_t index; X register int base, cmp, lim; X register PAGE *h; X pgno_t pg; X static EPG e; X X BT_CLR(t); X for (pg = P_ROOT;;) { X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (NULL); X X /* Do a binary search on the current page. */ X e.page = h; X for (base = 0, lim = NEXTINDEX(h); lim; lim >>= 1) { X e.index = index = base + (lim >> 1); X if ((cmp = __bt_cmp(t, key, &e)) == 0) { X if (h->flags & P_BLEAF) { X *exactp = 1; X return (&e); X } X goto next; X } X if (cmp > 0) { X base = index + 1; X --lim; X } X } X X /* If it's a leaf page, we're done. */ X if (h->flags & P_BLEAF) { X e.index = base; X *exactp = 0; X return (&e); X } X X /* X * No match found. Base is the smallest index greater than X * key and may be zero or a last + 1 index. If it's non-zero, X * decrement by one, and record the internal page which should X * be a parent page for the key. If a split later occurs, the X * inserted page will be to the right of the saved page. X */ X index = base ? base - 1 : base; X Xnext: if (__bt_push(t, h->pgno, index) == RET_ERROR) X return (NULL); X pg = GETBINTERNAL(h, index)->pgno; X mpool_put(t->bt_mp, h, 0); X } X} END_OF_FILE if test 3809 -ne `wc -c <'btree/bt_search.c'`; then echo shar: \"'btree/bt_search.c'\" unpacked with wrong size! fi # end of 'btree/bt_search.c' fi if test -f 'hash/hash_func.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'hash/hash_func.c'\" else echo shar: Extracting \"'hash/hash_func.c'\" \(4699 characters\) sed "s/^X//" >'hash/hash_func.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)hash_func.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X X#include X#include "hash.h" X#include "page.h" X#include "extern.h" X Xstatic int hash1 __P((u_char *, int)); Xstatic int hash2 __P((u_char *, int)); Xstatic int hash3 __P((u_char *, int)); Xstatic int hash4 __P((u_char *, int)); X X/* Global default hash function */ Xint (*__default_hash) __P((u_char *, int)) = hash4; X X/******************************* HASH FUNCTIONS **************************/ X/* X * Assume that we've already split the bucket to which this key hashes, X * calculate that bucket, and check that in fact we did already split it. X * X * This came from ejb's hsearch. X */ X X#define PRIME1 37 X#define PRIME2 1048583 X Xstatic int Xhash1(key, len) X register u_char *key; X register int len; X{ X register int h; X X h = 0; X /* Convert string to integer */ X while (len--) X h = h * PRIME1 ^ (*key++ - ' '); X h %= PRIME2; X return (h); X} X X/* X * Phong's linear congruential hash X */ X#define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) X Xstatic int Xhash2(key, len) X register u_char *key; X int len; X{ X register u_char *e, c; X register int h; X X e = key + len; X for (h = 0; key != e;) { X c = *key++; X if (!c && key > e) X break; X dcharhash(h, c); X } X return (h); X} X X/* X * This is INCREDIBLY ugly, but fast. We break the string up into 8 byte X * units. On the first time through the loop we get the "leftover bytes" X * (strlen % 8). On every other iteration, we perform 8 HASHC's so we handle X * all 8 bytes. Essentially, this saves us 7 cmp & branch instructions. If X * this routine is heavily used enough, it's worth the ugly coding. X * X * OZ's original sdbm hash X */ Xstatic int Xhash3(key, len) X register u_char *key; X register int len; X{ X register int n, loop; X X#define HASHC n = *key++ + 65599 * n X X n = 0; X if (len > 0) { X loop = (len + 8 - 1) >> 3; X X switch (len & (8 - 1)) { X case 0: X do { /* All fall throughs */ X HASHC; X case 7: X HASHC; X case 6: X HASHC; X case 5: X HASHC; X case 4: X HASHC; X case 3: X HASHC; X case 2: X HASHC; X case 1: X HASHC; X } while (--loop); X } X X } X return (n); X} X X/* Hash function from Chris Torek. */ Xstatic int Xhash4(key, len) X register u_char *key; X register int len; X{ X register int h, loop; X X#define HASH4a h = (h << 5) - h + *key++; X#define HASH4b h = (h << 5) + h + *key++; X#define HASH4 HASH4b X X h = 0; X if (len > 0) { X loop = (len + 8 - 1) >> 3; X X switch (len & (8 - 1)) { X case 0: X do { /* All fall throughs */ X HASH4; X case 7: X HASH4; X case 6: X HASH4; X case 5: X HASH4; X case 4: X HASH4; X case 3: X HASH4; X case 2: X HASH4; X case 1: X HASH4; X } while (--loop); X } X X } X return (h); X} END_OF_FILE if test 4699 -ne `wc -c <'hash/hash_func.c'`; then echo shar: \"'hash/hash_func.c'\" unpacked with wrong size! fi # end of 'hash/hash_func.c' fi if test -f 'hash/ndbm.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'hash/ndbm.c'\" else echo shar: Extracting \"'hash/ndbm.c'\" \(4334 characters\) sed "s/^X//" >'hash/ndbm.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)ndbm.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X/* X * This package provides a dbm compatible interface to the new hashing X * package described in db(3). X */ X X#include X X#include X#include X#include X X#include "hash.h" X X/* X * Returns: X * *DBM on success X * NULL on failure X */ Xextern DBM * Xdbm_open(file, flags, mode) X const char *file; X int flags, mode; X{ X HASHINFO info; X char path[MAXPATHLEN]; X X info.bsize = 4096; X info.ffactor = 40; X info.nelem = 1; X info.cachesize = NULL; X info.hash = NULL; X info.lorder = 0; X (void)strcpy(path, file); X (void)strcat(path, DBM_SUFFIX); X return ((DBM *)__hash_open(path, flags, mode, &info)); X} X Xextern void Xdbm_close(db) X DBM *db; X{ X (void)(db->close)(db); X} X X/* X * Returns: X * DATUM on success X * NULL on failure X */ Xextern datum Xdbm_fetch(db, key) X DBM *db; X datum key; X{ X datum retval; X int status; X X status = (db->get)(db, (DBT *)&key, (DBT *)&retval, 0); X if (status) { X retval.dptr = NULL; X retval.dsize = 0; X } X return (retval); X} X X/* X * Returns: X * DATUM on success X * NULL on failure X */ Xextern datum Xdbm_firstkey(db) X DBM *db; X{ X int status; X datum retdata, retkey; X X status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_FIRST); X if (status) X retkey.dptr = NULL; X return (retkey); X} X X/* X * Returns: X * DATUM on success X * NULL on failure X */ Xextern datum Xdbm_nextkey(db) X DBM *db; X{ X int status; X datum retdata, retkey; X X status = (db->seq)(db, (DBT *)&retkey, (DBT *)&retdata, R_NEXT); X if (status) X retkey.dptr = NULL; X return (retkey); X} X/* X * Returns: X * 0 on success X * <0 failure X */ Xextern int Xdbm_delete(db, key) X DBM *db; X datum key; X{ X int status; X X status = (db->del)(db, (DBT *)&key, 0); X if (status) X return (-1); X else X return (0); X} X X/* X * Returns: X * 0 on success X * <0 failure X * 1 if DBM_INSERT and entry exists X */ Xextern int Xdbm_store(db, key, content, flags) X DBM *db; X datum key, content; X int flags; X{ X return ((db->put)(db, (DBT *)&key, (DBT *)&content, X (flags == DBM_INSERT) ? R_NOOVERWRITE : 0)); X} X Xextern int Xdbm_error(db) X DBM *db; X{ X HTAB *hp; X X hp = (HTAB *)db->internal; X return (hp->errno); X} X Xextern int Xdbm_clearerr(db) X DBM *db; X{ X HTAB *hp; X X hp = (HTAB *)db->internal; X hp->errno = 0; X return (0); X} X Xextern int Xdbm_dirfno(db) X DBM *db; X{ X return(((HTAB *)db->internal)->fp); X} END_OF_FILE if test 4334 -ne `wc -c <'hash/ndbm.c'`; then echo shar: \"'hash/ndbm.c'\" unpacked with wrong size! fi # end of 'hash/ndbm.c' fi if test -f 'hash/page.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'hash/page.h'\" else echo shar: Extracting \"'hash/page.h'\" \(3610 characters\) sed "s/^X//" >'hash/page.h' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X * X * @(#)page.h 8.1 (Berkeley) 6/6/93 X */ X X/* X * Definitions for hashing page file format. X */ X X/* X * routines dealing with a data page X * X * page format: X * +------------------------------+ X * p | n | keyoff | datoff | keyoff | X * +------------+--------+--------+ X * | datoff | free | ptr | --> | X * +--------+---------------------+ X * | F R E E A R E A | X * +--------------+---------------+ X * | <---- - - - | data | X * +--------+-----+----+----------+ X * | key | data | key | X * +--------+----------+----------+ X * X * Pointer to the free space is always: p[p[0] + 2] X * Amount of free space on the page is: p[p[0] + 1] X */ X X/* X * How many bytes required for this pair? X * 2 shorts in the table at the top of the page + room for the X * key and room for the data X * X * We prohibit entering a pair on a page unless there is also room to append X * an overflow page. The reason for this it that you can get in a situation X * where a single key/data pair fits on a page, but you can't append an X * overflow page and later you'd have to split the key/data and handle like X * a big pair. X * You might as well do this up front. X */ X X#define PAIRSIZE(K,D) (2*sizeof(u_short) + (K)->size + (D)->size) X#define BIGOVERHEAD (4*sizeof(u_short)) X#define KEYSIZE(K) (4*sizeof(u_short) + (K)->size); X#define OVFLSIZE (2*sizeof(u_short)) X#define FREESPACE(P) ((P)[(P)[0]+1]) X#define OFFSET(P) ((P)[(P)[0]+2]) X#define PAIRFITS(P,K,D) \ X (((P)[2] >= REAL_KEY) && \ X (PAIRSIZE((K),(D)) + OVFLSIZE) <= FREESPACE((P))) X#define PAGE_META(N) (((N)+3) * sizeof(u_short)) X Xtypedef struct { X BUFHEAD *newp; X BUFHEAD *oldp; X BUFHEAD *nextp; X u_short next_addr; X} SPLIT_RETURN; END_OF_FILE if test 3610 -ne `wc -c <'hash/page.h'`; then echo shar: \"'hash/page.h'\" unpacked with wrong size! fi # end of 'hash/page.h' fi if test -f 'man/hash.3' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'man/hash.3'\" else echo shar: Extracting \"'man/hash.3'\" \(5184 characters\) sed "s/^X//" >'man/hash.3' <<'END_OF_FILE' X.\" Copyright (c) 1990, 1993 X.\" The Regents of the University of California. All rights reserved. X.\" X.\" Redistribution and use in source and binary forms, with or without X.\" modification, are permitted provided that the following conditions X.\" are met: X.\" 1. Redistributions of source code must retain the above copyright X.\" notice, this list of conditions and the following disclaimer. X.\" 2. Redistributions in binary form must reproduce the above copyright X.\" notice, this list of conditions and the following disclaimer in the X.\" documentation and/or other materials provided with the distribution. X.\" 3. All advertising materials mentioning features or use of this software X.\" must display the following acknowledgement: X.\" This product includes software developed by the University of X.\" California, Berkeley and its contributors. X.\" 4. Neither the name of the University nor the names of its contributors X.\" may be used to endorse or promote products derived from this software X.\" without specific prior written permission. X.\" X.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X.\" SUCH DAMAGE. X.\" X.\" @(#)hash.3 8.1 (Berkeley) 6/6/93 X.\" X.TH HASH 3 "June 6, 1993" X.UC 7 X.SH NAME Xhash \- hash database access method X.SH SYNOPSIS X.nf X.ft B X#include X#include X.ft R X.fi X.SH DESCRIPTION XThe routine X.IR dbopen Xis the library interface to database files. XOne of the supported file formats is hash files. XThe general description of the database access methods is in X.IR dbopen (3), Xthis manual page describes only the hash specific information. X.PP XThe hash data structure is an extensible, dynamic hashing scheme. X.PP XThe access method specific data structure provided to X.I dbopen Xis defined in the include file as follows: X.sp Xtypedef struct { X.RS Xint bsize; X.br Xint cachesize; X.br Xint ffactor; X.br Xu_long (*hash)(const void *, size_t); X.br Xint lorder; X.br Xint nelem; X.RE X} HASHINFO; X.PP XThe elements of this structure are as follows: X.TP Xbsize X.I Bsize Xdefines the hash table bucket size, and is, by default, 256 bytes. XIt may be preferable to increase the page size for disk-resident tables Xand tables with large data items. X.TP Xcachesize XA suggested maximum size, in bytes, of the memory cache. XThis value is X.B only Xadvisory, and the access method will allocate more memory rather Xthan fail. X.TP Xffactor X.I Ffactor Xindicates a desired density within the hash table. XIt is an approximation of the number of keys allowed to accumulate in any Xone bucket, determining when the hash table grows or shrinks. XThe default value is 8. X.TP Xhash X.I Hash Xis a user defined hash function. XSince no hash function performs equally well on all possible data, the Xuser may find that the built-in hash function does poorly on a particular Xdata set. XUser specified hash functions must take two arguments (a pointer to a byte Xstring and a length) and return an u_long to be used as the hash value. X.TP Xlorder XThe byte order for integers in the stored database metadata. XThe number should represent the order as an integer; for example, Xbig endian order would be the number 4,321. XIf X.I lorder Xis 0 (no order is specified) the current host order is used. XIf the file already exists, the specified value is ignored and the Xvalue specified when the tree was created is used. X.TP Xnelem X.I Nelem Xis an estimate of the final size of the hash table. XIf not set or set too low, hash tables will expand gracefully as keys Xare entered, although a slight performance degradation may be noticed. XThe default value is 1. X.PP XIf the file already exists (and the O_TRUNC flag is not specified), the Xvalues specified for the parameters bsize, ffactor, lorder and nelem are Xignored and the values specified when the tree was created are used. X.PP XIf a hash function is specified, X.I hash_open Xwill attempt to determine if the hash function specified is the same as Xthe one with which the database was created, and will fail if it is not. X.PP XBackward compatible interfaces to the routines described in X.IR dbm (3), Xand X.IR ndbm (3) Xare provided, however, these interfaces are not compatible with Xprevious file formats. X.SH "SEE ALSO" X.IR btree (3), X.IR dbopen (3), X.IR mpool (3), X.IR recno (3) X.br X.IR "Dynamic Hash Tables" , XPer-Ake Larson, Communications of the ACM, April 1988. X.br X.IR "A New Hash Package for UNIX" , XMargo Seltzer, USENIX Proceedings, Winter 1991. X.SH BUGS XOnly big and little endian byte order is supported. END_OF_FILE if test 5184 -ne `wc -c <'man/hash.3'`; then echo shar: \"'man/hash.3'\" unpacked with wrong size! fi # end of 'man/hash.3' fi if test -f 'recno/rec_close.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'recno/rec_close.c'\" else echo shar: Extracting \"'recno/rec_close.c'\" \(4186 characters\) sed "s/^X//" >'recno/rec_close.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)rec_close.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X#include X#include X X#include X#include X#include X#include X X#include X#include "recno.h" X X/* X * __REC_CLOSE -- Close a recno tree. X * X * Parameters: X * dbp: pointer to access method X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xint X__rec_close(dbp) X DB *dbp; X{ X BTREE *t; X int rval; X X if (__rec_sync(dbp, 0) == RET_ERROR) X return (RET_ERROR); X X /* Committed to closing. */ X t = dbp->internal; X X rval = RET_SUCCESS; X if (ISSET(t, R_MEMMAPPED) && munmap(t->bt_smap, t->bt_msize)) X rval = RET_ERROR; X X if (!ISSET(t, R_INMEM)) X if (ISSET(t, R_CLOSEFP)) { X if (fclose(t->bt_rfp)) X rval = RET_ERROR; X } else X if (close(t->bt_rfd)) X rval = RET_ERROR; X X if (__bt_close(dbp) == RET_ERROR) X rval = RET_ERROR; X X return (rval); X} X X/* X * __REC_SYNC -- sync the recno tree to disk. X * X * Parameters: X * dbp: pointer to access method X * X * Returns: X * RET_SUCCESS, RET_ERROR. X */ Xint X__rec_sync(dbp, flags) X const DB *dbp; X u_int flags; X{ X struct iovec iov[2]; X BTREE *t; X DBT data, key; X off_t off; X recno_t scursor, trec; X int status; X X t = dbp->internal; X X if (flags == R_RECNOSYNC) X return (__bt_sync(dbp, 0)); X X if (ISSET(t, R_RDONLY | R_INMEM) || !ISSET(t, R_MODIFIED)) X return (RET_SUCCESS); X X /* Read any remaining records into the tree. */ X if (!ISSET(t, R_EOF) && t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR) X return (RET_ERROR); X X /* Rewind the file descriptor. */ X if (lseek(t->bt_rfd, (off_t)0, SEEK_SET) != 0) X return (RET_ERROR); X X iov[1].iov_base = "\n"; X iov[1].iov_len = 1; X scursor = t->bt_rcursor; X X key.size = sizeof(recno_t); X key.data = &trec; X X status = (dbp->seq)(dbp, &key, &data, R_FIRST); X while (status == RET_SUCCESS) { X iov[0].iov_base = data.data; X iov[0].iov_len = data.size; X if (writev(t->bt_rfd, iov, 2) != data.size + 1) X return (RET_ERROR); X status = (dbp->seq)(dbp, &key, &data, R_NEXT); X } X t->bt_rcursor = scursor; X if (status == RET_ERROR) X return (RET_ERROR); X if ((off = lseek(t->bt_rfd, (off_t)0, SEEK_CUR)) == -1) X return (RET_ERROR); X if (ftruncate(t->bt_rfd, off)) X return (RET_ERROR); X CLR(t, R_MODIFIED); X return (RET_SUCCESS); X} END_OF_FILE if test 4186 -ne `wc -c <'recno/rec_close.c'`; then echo shar: \"'recno/rec_close.c'\" unpacked with wrong size! fi # end of 'recno/rec_close.c' fi if test -f 'recno/rec_delete.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'recno/rec_delete.c'\" else echo shar: Extracting \"'recno/rec_delete.c'\" \(5406 characters\) sed "s/^X//" >'recno/rec_delete.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Mike Olson. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)rec_delete.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X X#include X#include X#include X X#include X#include "recno.h" X Xstatic int rec_rdelete __P((BTREE *, recno_t)); X X/* X * __REC_DELETE -- Delete the item(s) referenced by a key. X * X * Parameters: X * dbp: pointer to access method X * key: key to delete X * flags: R_CURSOR if deleting what the cursor references X * X * Returns: X * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. X */ Xint X__rec_delete(dbp, key, flags) X const DB *dbp; X const DBT *key; X u_int flags; X{ X BTREE *t; X recno_t nrec; X int status; X X t = dbp->internal; X switch(flags) { X case 0: X if ((nrec = *(recno_t *)key->data) == 0) X goto einval; X if (nrec > t->bt_nrecs) X return (RET_SPECIAL); X --nrec; X status = rec_rdelete(t, nrec); X break; X case R_CURSOR: X if (!ISSET(t, B_SEQINIT)) X goto einval; X if (t->bt_nrecs == 0) X return (RET_SPECIAL); X status = rec_rdelete(t, t->bt_rcursor - 1); X if (status == RET_SUCCESS) X --t->bt_rcursor; X break; X default: Xeinval: errno = EINVAL; X return (RET_ERROR); X } X X if (status == RET_SUCCESS) X SET(t, B_MODIFIED | R_MODIFIED); X return (status); X} X X/* X * REC_RDELETE -- Delete the data matching the specified key. X * X * Parameters: X * tree: tree X * nrec: record to delete X * X * Returns: X * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. X */ Xstatic int Xrec_rdelete(t, nrec) X BTREE *t; X recno_t nrec; X{ X EPG *e; X PAGE *h; X int status; X X /* Find the record; __rec_search pins the page. */ X if ((e = __rec_search(t, nrec, SDELETE)) == NULL) { X mpool_put(t->bt_mp, e->page, 0); X return (RET_ERROR); X } X X /* Delete the record. */ X h = e->page; X status = __rec_dleaf(t, h, e->index); X if (status != RET_SUCCESS) { X mpool_put(t->bt_mp, h, 0); X return (status); X } X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X return (RET_SUCCESS); X} X X/* X * __REC_DLEAF -- Delete a single record from a recno leaf page. X * X * Parameters: X * t: tree X * index: index on current page to delete X * X * Returns: X * RET_SUCCESS, RET_ERROR. X */ Xint X__rec_dleaf(t, h, index) X BTREE *t; X PAGE *h; X int index; X{ X register RLEAF *rl; X register indx_t *ip, offset; X register size_t nbytes; X register int cnt; X char *from; X void *to; X X /* X * Delete a record from a recno leaf page. Internal records are never X * deleted from internal pages, regardless of the records that caused X * them to be added being deleted. Pages made empty by deletion are X * not reclaimed. They are, however, made available for reuse. X * X * Pack the remaining entries at the end of the page, shift the indices X * down, overwriting the deleted record and its index. If the record X * uses overflow pages, make them available for reuse. X */ X to = rl = GETRLEAF(h, index); X if (rl->flags & P_BIGDATA && __ovfl_delete(t, rl->bytes) == RET_ERROR) X return (RET_ERROR); X nbytes = NRLEAF(rl); X X /* X * Compress the key/data pairs. Compress and adjust the [BR]LEAF X * offsets. Reset the headers. X */ X from = (char *)h + h->upper; X memmove(from + nbytes, from, (char *)to - from); X h->upper += nbytes; X X offset = h->linp[index]; X for (cnt = &h->linp[index] - (ip = &h->linp[0]); cnt--; ++ip) X if (ip[0] < offset) X ip[0] += nbytes; X for (cnt = &h->linp[NEXTINDEX(h)] - ip; --cnt; ++ip) X ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; X h->lower -= sizeof(indx_t); X --t->bt_nrecs; X return (RET_SUCCESS); X} END_OF_FILE if test 5406 -ne `wc -c <'recno/rec_delete.c'`; then echo shar: \"'recno/rec_delete.c'\" unpacked with wrong size! fi # end of 'recno/rec_delete.c' fi if test -f 'recno/rec_search.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'recno/rec_search.c'\" else echo shar: Extracting \"'recno/rec_search.c'\" \(3852 characters\) sed "s/^X//" >'recno/rec_search.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)rec_search.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include X X#include X#include X X#include X#include "recno.h" X X/* X * __REC_SEARCH -- Search a btree for a key. X * X * Parameters: X * t: tree to search X * recno: key to find X * op: search operation X * X * Returns: X * EPG for matching record, if any, or the EPG for the location of the X * key, if it were inserted into the tree. X * X * Warnings: X * The EPG returned is in static memory, and will be overwritten by the X * next search of any kind in any tree. X */ XEPG * X__rec_search(t, recno, op) X BTREE *t; X recno_t recno; X enum SRCHOP op; X{ X static EPG e; X register indx_t index; X register PAGE *h; X EPGNO *parent; X RINTERNAL *r; X pgno_t pg; X indx_t top; X recno_t total; X int serrno; X X BT_CLR(t); X for (pg = P_ROOT, total = 0;;) { X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X goto err; X if (h->flags & P_RLEAF) { X e.page = h; X e.index = recno - total; X return (&e); X } X for (index = 0, top = NEXTINDEX(h);;) { X r = GETRINTERNAL(h, index); X if (++index == top || total + r->nrecs > recno) X break; X total += r->nrecs; X } X X if (__bt_push(t, pg, index - 1) == RET_ERROR) X return (NULL); X X pg = r->pgno; X switch (op) { X case SDELETE: X --GETRINTERNAL(h, (index - 1))->nrecs; X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X break; X case SINSERT: X ++GETRINTERNAL(h, (index - 1))->nrecs; X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X break; X case SEARCH: X mpool_put(t->bt_mp, h, 0); X break; X } X X } X /* Try and recover the tree. */ Xerr: serrno = errno; X if (op != SEARCH) X while ((parent = BT_POP(t)) != NULL) { X if ((h = mpool_get(t->bt_mp, parent->pgno, 0)) == NULL) X break; X if (op == SINSERT) X --GETRINTERNAL(h, parent->index)->nrecs; X else X ++GETRINTERNAL(h, parent->index)->nrecs; X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X } X errno = serrno; X return (NULL); X} END_OF_FILE if test 3852 -ne `wc -c <'recno/rec_search.c'`; then echo shar: \"'recno/rec_search.c'\" unpacked with wrong size! fi # end of 'recno/rec_search.c' fi if test -f 'recno/rec_seq.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'recno/rec_seq.c'\" else echo shar: Extracting \"'recno/rec_seq.c'\" \(3591 characters\) sed "s/^X//" >'recno/rec_seq.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#ifndef lint Xstatic char sccsid[] = "@(#)rec_seq.c 8.1 (Berkeley) 6/4/93"; X#endif /* not lint */ X X#include X X#include X#include X#include X#include X X#include X#include "recno.h" X X/* X * __REC_SEQ -- Recno sequential scan interface. X * X * Parameters: X * dbp: pointer to access method X * key: key for positioning and return value X * data: data return value X * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV. X * X * Returns: X * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. X */ Xint X__rec_seq(dbp, key, data, flags) X const DB *dbp; X DBT *key, *data; X u_int flags; X{ X BTREE *t; X EPG *e; X recno_t nrec; X int status; X X t = dbp->internal; X switch(flags) { X case R_CURSOR: X if ((nrec = *(recno_t *)key->data) == 0) X goto einval; X break; X case R_NEXT: X if (ISSET(t, B_SEQINIT)) { X nrec = t->bt_rcursor + 1; X break; X } X /* FALLTHROUGH */ X case R_FIRST: X nrec = 1; X break; X case R_PREV: X if (ISSET(t, B_SEQINIT)) { X if ((nrec = t->bt_rcursor - 1) == 0) X return (RET_SPECIAL); X break; X } X /* FALLTHROUGH */ X case R_LAST: X if (!ISSET(t, R_EOF | R_INMEM) && X t->bt_irec(t, MAX_REC_NUMBER) == RET_ERROR) X return (RET_ERROR); X nrec = t->bt_nrecs; X break; X default: Xeinval: errno = EINVAL; X return (RET_ERROR); X } X X if (t->bt_nrecs == 0 || nrec > t->bt_nrecs) { X if (!ISSET(t, R_EOF | R_INMEM) && X (status = t->bt_irec(t, nrec)) != RET_SUCCESS) X return (status); X if (t->bt_nrecs == 0 || nrec > t->bt_nrecs) X return (RET_SPECIAL); X } X X if ((e = __rec_search(t, nrec - 1, SEARCH)) == NULL) X return (RET_ERROR); X X SET(t, B_SEQINIT); X t->bt_rcursor = nrec; X X status = __rec_ret(t, e, nrec, key, data); X X mpool_put(t->bt_mp, e->page, 0); X return (status); X} END_OF_FILE if test 3591 -ne `wc -c <'recno/rec_seq.c'`; then echo shar: \"'recno/rec_seq.c'\" unpacked with wrong size! fi # end of 'recno/rec_seq.c' fi if test -f 'test/hash.tests/driver2.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'test/hash.tests/driver2.c'\" else echo shar: Extracting \"'test/hash.tests/driver2.c'\" \(3531 characters\) sed "s/^X//" >'test/hash.tests/driver2.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#ifndef lint Xstatic char copyright[] = X"@(#) Copyright (c) 1991, 1993\n\ X The Regents of the University of California. All rights reserved.\n"; X#endif /* not lint */ X X#ifndef lint Xstatic char sccsid[] = "@(#)driver2.c 8.1 (Berkeley) 6/4/93"; X#endif /* not lint */ X X/* X * Test driver, to try to tackle the large ugly-split problem. X */ X X#include X#include X#include "ndbm.h" X Xint my_hash(key, len) X char *key; X int len; X{ X return(17); /* So I'm cruel... */ X} X Xmain(argc, argv) X int argc; X{ X DB *db; X DBT key, content; X char keybuf[2049]; X char contentbuf[2049]; X char buf[256]; X int i; X HASHINFO info; X X info.bsize = 1024; X info.ffactor = 5; X info.nelem = 1; X info.cachesize = NULL; X#ifdef HASH_ID_PROGRAM_SPECIFIED X info.hash_id = HASH_ID_PROGRAM_SPECIFIED; X info.hash_func = my_hash; X#else X info.hash = my_hash; X#endif X info.lorder = 0; X if (!(db = dbopen("bigtest", O_RDWR | O_CREAT, 0644, DB_HASH, &info))) { X sprintf(buf, "dbopen: failed on file bigtest"); X perror(buf); X exit(1); X } X srandom(17); X key.data = keybuf; X content.data = contentbuf; X bzero(keybuf, sizeof(keybuf)); X bzero(contentbuf, sizeof(contentbuf)); X for (i=1; i <= 500; i++) { X key.size = 128 + (random()&1023); X content.size = 128 + (random()&1023); X/* printf("%d: Key size %d, data size %d\n", i, key.size, X content.size); */ X sprintf(keybuf, "Key #%d", i); X sprintf(contentbuf, "Contents #%d", i); X if ((db->put)(db, &key, &content, R_NOOVERWRITE)) { X sprintf(buf, "dbm_store #%d", i); X perror(buf); X } X } X if ((db->close)(db)) { X perror("closing hash file"); X exit(1); X } X exit(0); X} X X X END_OF_FILE if test 3531 -ne `wc -c <'test/hash.tests/driver2.c'`; then echo shar: \"'test/hash.tests/driver2.c'\" unpacked with wrong size! fi # end of 'test/hash.tests/driver2.c' fi if test -f 'test/hash.tests/tdel.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'test/hash.tests/tdel.c'\" else echo shar: Extracting \"'test/hash.tests/tdel.c'\" \(3671 characters\) sed "s/^X//" >'test/hash.tests/tdel.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#ifndef lint Xstatic char copyright[] = X"@(#) Copyright (c) 1991, 1993\n\ X The Regents of the University of California. All rights reserved.\n"; X#endif /* not lint */ X X#ifndef lint Xstatic char sccsid[] = "@(#)tdel.c 8.1 (Berkeley) 6/4/93"; X#endif /* not lint */ X X#include X#include X#include X#include X X#define INITIAL 25000 X#define MAXWORDS 25000 /* # of elements in search table */ X X/* Usage: thash pagesize fillfactor file */ Xchar wp1[8192]; Xchar wp2[8192]; Xmain(argc, argv) Xchar **argv; X{ X DBT item, key; X DB *dbp; X HASHINFO ctl; X FILE *fp; X int stat; X X int i = 0; X X argv++; X ctl.nelem = INITIAL; X ctl.hash = NULL; X ctl.bsize = atoi(*argv++); X ctl.ffactor = atoi(*argv++); X ctl.cachesize = 1024 * 1024; /* 1 MEG */ X ctl.lorder = 0; X argc -= 2; X if (!(dbp = dbopen( NULL, O_CREAT|O_RDWR, 0400, DB_HASH, &ctl))) { X /* create table */ X fprintf(stderr, "cannot create: hash table size %d)\n", X INITIAL); X exit(1); X } X X key.data = wp1; X item.data = wp2; X while ( fgets(wp1, 8192, stdin) && X fgets(wp2, 8192, stdin) && X i++ < MAXWORDS) { X/* X* put info in structure, and structure in the item X*/ X key.size = strlen(wp1); X item.size = strlen(wp2); X X/* X * enter key/data pair into the table X */ X if ((dbp->put)(dbp, &key, &item, R_NOOVERWRITE) != NULL) { X fprintf(stderr, "cannot enter: key %s\n", X item.data); X exit(1); X } X } X X if ( --argc ) { X fp = fopen ( argv[0], "r"); X i = 0; X while ( fgets(wp1, 8192, fp) && X fgets(wp2, 8192, fp) && X i++ < MAXWORDS) { X key.size = strlen(wp1); X stat = (dbp->del)(dbp, &key, 0); X if (stat) { X fprintf ( stderr, "Error retrieving %s\n", key.data ); X exit(1); X } X } X fclose(fp); X } X (dbp->close)(dbp); X exit(0); X} END_OF_FILE if test 3671 -ne `wc -c <'test/hash.tests/tdel.c'`; then echo shar: \"'test/hash.tests/tdel.c'\" unpacked with wrong size! fi # end of 'test/hash.tests/tdel.c' fi if test -f 'test/hash.tests/thash4.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'test/hash.tests/thash4.c'\" else echo shar: Extracting \"'test/hash.tests/thash4.c'\" \(3996 characters\) sed "s/^X//" >'test/hash.tests/thash4.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1991, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#ifndef lint Xstatic char copyright[] = X"@(#) Copyright (c) 1991, 1993\n\ X The Regents of the University of California. All rights reserved.\n"; X#endif /* not lint */ X X#ifndef lint Xstatic char sccsid[] = "@(#)thash4.c 8.1 (Berkeley) 6/4/93"; X#endif /* not lint */ X X#include X#include X#include X#include X#include X#include X X#define INITIAL 25000 X#define MAXWORDS 25000 /* # of elements in search table */ X X/* Usage: thash pagesize fillfactor file */ Xchar wp1[8192]; Xchar wp2[8192]; Xmain(argc, argv) Xchar **argv; X{ X DBT item, key, res; X DB *dbp; X HASHINFO ctl; X FILE *fp; X int stat; X time_t t; X X int i = 0; X X argv++; X ctl.hash = NULL; X ctl.bsize = atoi(*argv++); X ctl.ffactor = atoi(*argv++); X ctl.nelem = atoi(*argv++); X ctl.cachesize = atoi(*argv++); X ctl.lorder = 0; X if (!(dbp = dbopen( NULL, O_CREAT|O_RDWR, 0400, DB_HASH, &ctl))) { X /* create table */ X fprintf(stderr, "cannot create: hash table size %d)\n", X INITIAL); X fprintf(stderr, "\terrno: %d\n", errno); X exit(1); X } X X key.data = wp1; X item.data = wp2; X while ( fgets(wp1, 8192, stdin) && X fgets(wp2, 8192, stdin) && X i++ < MAXWORDS) { X/* X* put info in structure, and structure in the item X*/ X key.size = strlen(wp1); X item.size = strlen(wp2); X X/* X * enter key/data pair into the table X */ X if ((dbp->put)(dbp, &key, &item, R_NOOVERWRITE) != NULL) { X fprintf(stderr, "cannot enter: key %s\n", X item.data); X fprintf(stderr, "\terrno: %d\n", errno); X exit(1); X } X } X X if ( --argc ) { X fp = fopen ( argv[0], "r"); X i = 0; X while ( fgets(wp1, 256, fp) && X fgets(wp2, 8192, fp) && X i++ < MAXWORDS) { X X key.size = strlen(wp1); X stat = (dbp->get)(dbp, &key, &res, 0); X if (stat < 0 ) { X fprintf ( stderr, "Error retrieving %s\n", key.data ); X fprintf(stderr, "\terrno: %d\n", errno); X exit(1); X } else if ( stat > 0 ) { X fprintf ( stderr, "%s not found\n", key.data ); X fprintf(stderr, "\terrno: %d\n", errno); X exit(1); X } X } X fclose(fp); X } X dbp->close(dbp); X exit(0); X} END_OF_FILE if test 3996 -ne `wc -c <'test/hash.tests/thash4.c'`; then echo shar: \"'test/hash.tests/thash4.c'\" unpacked with wrong size! fi # end of 'test/hash.tests/thash4.c' fi echo shar: End of archive 2 \(of 9\). cp /dev/null ark2isdone MISSING="" for I in 1 2 3 4 5 6 7 8 9 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 9 archives. rm -f ark[1-9]isdone ark[1-9][0-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0