Usenet 1994 January

home *** CD-ROM | disk | FTP | other *** search

/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume26 / db-1.6 / part04 < prev next >

Wrap

Text File | 1993-07-05 | 94.3 KB | 3,344 lines

Newsgroups: comp.sources.unix From: bostic@cs.berkeley.edu (Keith Bostic) Subject: v26i283: db-1.6 - A New Hashing Package for UNIX(tm) (updates dbm/ndbm), Part04/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 283 Archive-Name: db-1.6/part04 #! /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 <file", e.g.. If this archive is complete, you # will see the following message at the end: # "End of archive 4 (of 9)." # Contents: btree/bt_debug.c btree/bt_delete.c btree/bt_open.c # btree/bt_put.c btree/bt_seq.c doc/hash.3.ps hash/hash.h # hash/hash_buf.c mpool/mpool.c # Wrapped by vixie@gw.home.vix.com on Mon Jul 5 15:27:24 1993 PATH=/bin:/usr/bin:/usr/ucb ; export PATH if test -f 'btree/bt_debug.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_debug.c'\" else echo shar: Extracting \"'btree/bt_debug.c'\" $8734 characters$ sed "s/^X//" >'btree/bt_debug.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_debug.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include <sys/param.h> X X#include <stdio.h> X#include <stdlib.h> X#include <string.h> X X#include <db.h> X#include "btree.h" X X#ifdef DEBUG X/* X * BT_DUMP -- Dump the tree X * X * Parameters: X * dbp: pointer to the DB X */ Xvoid X__bt_dump(dbp) X DB *dbp; X{ X BTREE *t; X PAGE *h; X pgno_t i; X char *sep; X X t = dbp->internal; X (void)fprintf(stderr, "%s: pgsz %d", X ISSET(t, B_INMEM) ? "memory" : "disk", t->bt_psize); X if (ISSET(t, R_RECNO)) X (void)fprintf(stderr, " keys %lu", t->bt_nrecs); X#undef X X#define X(flag, name) \ X if (ISSET(t, flag)) { \ X (void)fprintf(stderr, "%s%s", sep, name); \ X sep = ", "; \ X } X if (t->bt_flags) { X sep = " flags ("; X X(B_DELCRSR, "DELCRSR"); X X(R_FIXLEN, "FIXLEN"); X X(B_INMEM, "INMEM"); X X(B_NODUPS, "NODUPS"); X X(B_RDONLY, "RDONLY"); X X(R_RECNO, "RECNO"); X X(B_SEQINIT, "SEQINIT"); X X(B_METADIRTY,"METADIRTY"); X (void)fprintf(stderr, ")\n"); X } X#undef X X X for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) { X __bt_dpage(h); X (void)mpool_put(t->bt_mp, h, 0); X } X} X X/* X * BT_DMPAGE -- Dump the meta page X * X * Parameters: X * h: pointer to the PAGE X */ Xvoid X__bt_dmpage(h) X PAGE *h; X{ X BTMETA *m; X char *sep; X X m = (BTMETA *)h; X (void)fprintf(stderr, "magic %lx\n", m->m_magic); X (void)fprintf(stderr, "version %lu\n", m->m_version); X (void)fprintf(stderr, "psize %lu\n", m->m_psize); X (void)fprintf(stderr, "free %lu\n", m->m_free); X (void)fprintf(stderr, "nrecs %lu\n", m->m_nrecs); X (void)fprintf(stderr, "flags %lu", m->m_flags); X#undef X X#define X(flag, name) \ X if (m->m_flags & flag) { \ X (void)fprintf(stderr, "%s%s", sep, name); \ X sep = ", "; \ X } X if (m->m_flags) { X sep = " ("; X X(B_NODUPS, "NODUPS"); X X(R_RECNO, "RECNO"); X (void)fprintf(stderr, ")"); X } X} X X/* X * BT_DNPAGE -- Dump the page X * X * Parameters: X * n: page number to dump. X */ Xvoid X__bt_dnpage(dbp, pgno) X DB *dbp; X pgno_t pgno; X{ X BTREE *t; X PAGE *h; X X t = dbp->internal; X if ((h = mpool_get(t->bt_mp, pgno, 0)) != NULL) { X __bt_dpage(h); X (void)mpool_put(t->bt_mp, h, 0); X } X} X X/* X * BT_DPAGE -- Dump the page X * X * Parameters: X * h: pointer to the PAGE X */ Xvoid X__bt_dpage(h) X PAGE *h; X{ X BINTERNAL *bi; X BLEAF *bl; X RINTERNAL *ri; X RLEAF *rl; X indx_t cur, top; X char *sep; X X (void)fprintf(stderr, " page %d: (", h->pgno); X#undef X X#define X(flag, name) \ X if (h->flags & flag) { \ X (void)fprintf(stderr, "%s%s", sep, name); \ X sep = ", "; \ X } X sep = ""; X X(P_BINTERNAL, "BINTERNAL") /* types */ X X(P_BLEAF, "BLEAF") X X(P_RINTERNAL, "RINTERNAL") /* types */ X X(P_RLEAF, "RLEAF") X X(P_OVERFLOW, "OVERFLOW") X X(P_PRESERVE, "PRESERVE"); X (void)fprintf(stderr, ")\n"); X#undef X X X (void)fprintf(stderr, "\tprev %2d next %2d", h->prevpg, h->nextpg); X if (h->flags & P_OVERFLOW) X return; X X top = NEXTINDEX(h); X (void)fprintf(stderr, " lower %3d upper %3d nextind %d\n", X h->lower, h->upper, top); X for (cur = 0; cur < top; cur++) { X (void)fprintf(stderr, "\t[%03d] %4d ", cur, h->linp[cur]); X switch(h->flags & P_TYPE) { X case P_BINTERNAL: X bi = GETBINTERNAL(h, cur); X (void)fprintf(stderr, X "size %03d pgno %03d", bi->ksize, bi->pgno); X if (bi->flags & P_BIGKEY) X (void)fprintf(stderr, " (indirect)"); X else if (bi->ksize) X (void)fprintf(stderr, X " {%.*s}", (int)bi->ksize, bi->bytes); X break; X case P_RINTERNAL: X ri = GETRINTERNAL(h, cur); X (void)fprintf(stderr, "entries %03d pgno %03d", X ri->nrecs, ri->pgno); X break; X case P_BLEAF: X bl = GETBLEAF(h, cur); X if (bl->flags & P_BIGKEY) X (void)fprintf(stderr, X "big key page %lu size %u/", X *(pgno_t *)bl->bytes, X *(size_t *)(bl->bytes + sizeof(pgno_t))); X else if (bl->ksize) X (void)fprintf(stderr, "%s/", bl->bytes); X if (bl->flags & P_BIGDATA) X (void)fprintf(stderr, X "big data page %lu size %u", X *(pgno_t *)(bl->bytes + bl->ksize), X *(size_t *)(bl->bytes + bl->ksize + X sizeof(pgno_t))); X else if (bl->dsize) X (void)fprintf(stderr, "%.*s", X (int)bl->dsize, bl->bytes + bl->ksize); X break; X case P_RLEAF: X rl = GETRLEAF(h, cur); X if (rl->flags & P_BIGDATA) X (void)fprintf(stderr, X "big data page %lu size %u", X *(pgno_t *)rl->bytes, X *(size_t *)(rl->bytes + sizeof(pgno_t))); X else if (rl->dsize) X (void)fprintf(stderr, X "%.*s", (int)rl->dsize, rl->bytes); X break; X } X (void)fprintf(stderr, "\n"); X } X} X#endif X X#ifdef STATISTICS X/* X * BT_STAT -- Gather/print the tree statistics X * X * Parameters: X * dbp: pointer to the DB X */ Xvoid X__bt_stat(dbp) X DB *dbp; X{ X extern u_long bt_cache_hit, bt_cache_miss; X extern u_long bt_rootsplit, bt_split, bt_sortsplit; X extern u_long bt_pfxsaved; X BTREE *t; X PAGE *h; X pgno_t i, pcont, pinternal, pleaf; X u_long ifree, lfree, nkeys; X int levels; X X t = dbp->internal; X pcont = pinternal = pleaf = 0; X nkeys = ifree = lfree = 0; X for (i = P_ROOT; (h = mpool_get(t->bt_mp, i, 0)) != NULL; ++i) { X switch(h->flags & P_TYPE) { X case P_BINTERNAL: X case P_RINTERNAL: X ++pinternal; X ifree += h->upper - h->lower; X break; X case P_BLEAF: X case P_RLEAF: X ++pleaf; X lfree += h->upper - h->lower; X nkeys += NEXTINDEX(h); X break; X case P_OVERFLOW: X ++pcont; X break; X } X (void)mpool_put(t->bt_mp, h, 0); X } X X /* Count the levels of the tree. */ X for (i = P_ROOT, levels = 0 ;; ++levels) { X h = mpool_get(t->bt_mp, i, 0); X if (h->flags & (P_BLEAF|P_RLEAF)) { X if (levels == 0) X levels = 1; X (void)mpool_put(t->bt_mp, h, 0); X break; X } X i = ISSET(t, R_RECNO) ? X GETRINTERNAL(h, 0)->pgno : X GETBINTERNAL(h, 0)->pgno; X (void)mpool_put(t->bt_mp, h, 0); X } X X (void)fprintf(stderr, "%d level%s with %ld keys", X levels, levels == 1 ? "" : "s", nkeys); X if (ISSET(t, R_RECNO)) X (void)fprintf(stderr, " (%ld header count)", t->bt_nrecs); X (void)fprintf(stderr, X "\n%lu pages (leaf %ld, internal %ld, overflow %ld)\n", X pinternal + pleaf + pcont, pleaf, pinternal, pcont); X (void)fprintf(stderr, "%ld cache hits, %ld cache misses\n", X bt_cache_hit, bt_cache_miss); X (void)fprintf(stderr, "%ld splits (%ld root splits, %ld sort splits)\n", X bt_split, bt_rootsplit, bt_sortsplit); X pleaf *= t->bt_psize - BTDATAOFF; X if (pleaf) X (void)fprintf(stderr, X "%.0f%% leaf fill (%ld bytes used, %ld bytes free)\n", X ((double)(pleaf - lfree) / pleaf) * 100, X pleaf - lfree, lfree); X pinternal *= t->bt_psize - BTDATAOFF; X if (pinternal) X (void)fprintf(stderr, X "%.0f%% internal fill (%ld bytes used, %ld bytes free\n", X ((double)(pinternal - ifree) / pinternal) * 100, X pinternal - ifree, ifree); X if (bt_pfxsaved) X (void)fprintf(stderr, "prefix checking removed %lu bytes.\n", X bt_pfxsaved); X} X#endif END_OF_FILE if test 8734 -ne `wc -c <'btree/bt_debug.c'`; then echo shar: \"'btree/bt_debug.c'\" unpacked with wrong size! fi # end of 'btree/bt_debug.c' fi if test -f 'btree/bt_delete.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_delete.c'\" else echo shar: Extracting \"'btree/bt_delete.c'\" $9222 characters$ sed "s/^X//" >'btree/bt_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[] = "@(#)bt_delete.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include <sys/types.h> X X#include <errno.h> X#include <stdio.h> X#include <string.h> X X#include <db.h> X#include "btree.h" X Xstatic int bt_bdelete __P((BTREE *, const DBT *)); X X/* X * __BT_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__bt_delete(dbp, key, flags) X const DB *dbp; X const DBT *key; X u_int flags; X{ X BTREE *t; X int status; X X t = dbp->internal; X if (ISSET(t, B_RDONLY)) { X errno = EPERM; X return (RET_ERROR); X } X switch(flags) { X case 0: X status = bt_bdelete(t, key); X break; X case R_CURSOR: X /* X * If flags is R_CURSOR, delete the cursor; must already have X * started a scan and not have already deleted the record. For X * the delete cursor bit to have been set requires that the X * scan be initialized, so no reason to check. X */ X if (!ISSET(t, B_SEQINIT)) X goto einval; X status = ISSET(t, B_DELCRSR) ? X RET_SPECIAL : __bt_crsrdel(t, &t->bt_bcursor); X break; X default: Xeinval: errno = EINVAL; X return (RET_ERROR); X } X if (status == RET_SUCCESS) X SET(t, B_MODIFIED); X return (status); X} X X/* X * BT_BDELETE -- Delete all key/data pairs matching the specified key. X * X * Parameters: X * tree: tree X * key: key to delete X * X * Returns: X * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found. X */ Xstatic int Xbt_bdelete(t, key) X BTREE *t; X const DBT *key; X{ X EPG *e, save; X PAGE *h; X pgno_t cpgno, pg; X indx_t cindex; X int deleted, dirty1, dirty2, exact; X X /* Find any matching record; __bt_search pins the page. */ X if ((e = __bt_search(t, key, &exact)) == NULL) X return (RET_ERROR); X if (!exact) { X mpool_put(t->bt_mp, e->page, 0); X return (RET_SPECIAL); X } X X /* X * Delete forward, then delete backward, from the found key. The X * ordering is so that the deletions don't mess up the page refs. X * The first loop deletes the key from the original page, the second X * unpins the original page. In the first loop, dirty1 is set if X * the original page is modified, and dirty2 is set if any subsequent X * pages are modified. In the second loop, dirty1 starts off set if X * the original page has been modified, and is set if any subsequent X * pages are modified. X * X * If find the key referenced by the cursor, don't delete it, just X * flag it for future deletion. The cursor page number is P_INVALID X * unless the sequential scan is initialized, so no reason to check. X * A special case is when the already deleted cursor record was the X * only record found. If so, then the delete opertion fails as no X * records were deleted. X * X * Cycle in place in the current page until the current record doesn't X * match the key or the page is empty. If the latter, walk forward, X * skipping empty pages and repeating until a record doesn't match X * the key or the end of the tree is reached. X */ X cpgno = t->bt_bcursor.pgno; X cindex = t->bt_bcursor.index; X save = *e; X dirty1 = 0; X for (h = e->page, deleted = 0;;) { X dirty2 = 0; X do { X if (h->pgno == cpgno && e->index == cindex) { X if (!ISSET(t, B_DELCRSR)) { X SET(t, B_DELCRSR); X deleted = 1; X } X ++e->index; X } else { X if (__bt_dleaf(t, h, e->index)) { X if (h->pgno != save.page->pgno) X mpool_put(t->bt_mp, h, dirty2); X mpool_put(t->bt_mp, save.page, dirty1); X return (RET_ERROR); X } X if (h->pgno == save.page->pgno) X dirty1 = MPOOL_DIRTY; X else X dirty2 = MPOOL_DIRTY; X deleted = 1; X } X } while (e->index < NEXTINDEX(h) && __bt_cmp(t, key, e) == 0); X X /* X * Quit if didn't find a match, no next page, or first key on X * the next page doesn't match. Don't unpin the original page X * unless an error occurs. X */ X if (e->index < NEXTINDEX(h)) X break; X for (;;) { X if ((pg = h->nextpg) == P_INVALID) X goto done1; X if (h->pgno != save.page->pgno) X mpool_put(t->bt_mp, h, dirty2); X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) { X mpool_put(t->bt_mp, save.page, dirty1); X return (RET_ERROR); X } X if (NEXTINDEX(h) != 0) { X e->page = h; X e->index = 0; X break; X } X } X X if (__bt_cmp(t, key, e) != 0) X break; X } X X /* X * Reach here with the original page and the last page referenced X * pinned (they may be the same). Release it if not the original. X */ Xdone1: if (h->pgno != save.page->pgno) X mpool_put(t->bt_mp, h, dirty2); X X /* X * Walk backwards from the record previous to the record returned by X * __bt_search, skipping empty pages, until a record doesn't match X * the key or reach the beginning of the tree. X */ X *e = save; X for (;;) { X if (e->index) X --e->index; X for (h = e->page; e->index; --e->index) { X if (__bt_cmp(t, key, e) != 0) X goto done2; X if (h->pgno == cpgno && e->index == cindex) { X if (!ISSET(t, B_DELCRSR)) { X SET(t, B_DELCRSR); X deleted = 1; X } X } else { X if (__bt_dleaf(t, h, e->index) == RET_ERROR) { X mpool_put(t->bt_mp, h, dirty1); X return (RET_ERROR); X } X if (h->pgno == save.page->pgno) X dirty1 = MPOOL_DIRTY; X deleted = 1; X } X } X X if ((pg = h->prevpg) == P_INVALID) X goto done2; X mpool_put(t->bt_mp, h, dirty1); X dirty1 = 0; X if ((e->page = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X e->index = NEXTINDEX(e->page); X } X X /* X * Reach here with the last page that was looked at pinned. Release X * it. X */ Xdone2: mpool_put(t->bt_mp, h, dirty1); X return (deleted ? RET_SUCCESS : RET_SPECIAL); X} X X/* X * __BT_DLEAF -- Delete a single record from a 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__bt_dleaf(t, h, index) X BTREE *t; X PAGE *h; X int index; X{ X register BLEAF *bl; 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 btree 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 = bl = GETBLEAF(h, index); X if (bl->flags & P_BIGKEY && __ovfl_delete(t, bl->bytes) == RET_ERROR) X return (RET_ERROR); X if (bl->flags & P_BIGDATA && X __ovfl_delete(t, bl->bytes + bl->ksize) == RET_ERROR) X return (RET_ERROR); X nbytes = NBLEAF(bl); 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 = index, ip = &h->linp[0]; cnt--; ++ip) X if (ip[0] < offset) X ip[0] += nbytes; X for (cnt = NEXTINDEX(h) - index; --cnt; ++ip) X ip[0] = ip[1] < offset ? ip[1] + nbytes : ip[1]; X h->lower -= sizeof(indx_t); X return (RET_SUCCESS); X} END_OF_FILE if test 9222 -ne `wc -c <'btree/bt_delete.c'`; then echo shar: \"'btree/bt_delete.c'\" unpacked with wrong size! fi # end of 'btree/bt_delete.c' fi if test -f 'btree/bt_open.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_open.c'\" else echo shar: Extracting \"'btree/bt_open.c'\" $10894 characters$ sed "s/^X//" >'btree/bt_open.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_open.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X/* X * Implementation of btree access method for 4.4BSD. X * X * The design here was originally based on that of the btree access method X * used in the Postgres database system at UC Berkeley. This implementation X * is wholly independent of the Postgres code. X */ X X#include <sys/param.h> X#include <sys/stat.h> X X#include <errno.h> X#include <fcntl.h> X#include <limits.h> X#include <signal.h> X#include <stdio.h> X#include <stdlib.h> X#include <string.h> X#include <unistd.h> X X#define __DBINTERFACE_PRIVATE X#include <db.h> X#include "btree.h" X Xstatic int byteorder __P((void)); Xstatic int nroot __P((BTREE *)); Xstatic int tmp __P((void)); X X/* X * __BT_OPEN -- Open a btree. X * X * Creates and fills a DB struct, and calls the routine that actually X * opens the btree. X * X * Parameters: X * fname: filename (NULL for in-memory trees) X * flags: open flag bits X * mode: open permission bits X * b: BTREEINFO pointer X * X * Returns: X * NULL on failure, pointer to DB on success. X * X */ XDB * X__bt_open(fname, flags, mode, openinfo) X const char *fname; X int flags, mode; X const BTREEINFO *openinfo; X{ X BTMETA m; X BTREE *t; X BTREEINFO b; X DB *dbp; X pgno_t ncache; X struct stat sb; X int machine_lorder, nr; X X t = NULL; X X /* X * Intention is to make sure all of the user's selections are okay X * here and then use them without checking. Can't be complete, since X * we don't know the right page size, lorder or flags until the backing X * file is opened. Also, the file's page size can cause the cachesize X * to change. X */ X machine_lorder = byteorder(); X if (openinfo) { X b = *openinfo; X X /* Flags: R_DUP. */ X if (b.flags & ~(R_DUP)) X goto einval; X X /* X * Page size must be indx_t aligned and >= MINPSIZE. Default X * page size is set farther on, based on the underlying file X * transfer size. X */ X if (b.psize && X (b.psize < MINPSIZE || b.psize > MAX_PAGE_OFFSET + 1 || X b.psize & sizeof(indx_t) - 1)) X goto einval; X X /* Minimum number of keys per page; absolute minimum is 2. */ X if (b.minkeypage) { X if (b.minkeypage < 2) X goto einval; X } else X b.minkeypage = DEFMINKEYPAGE; X X /* If no comparison, use default comparison and prefix. */ X if (b.compare == NULL) { X b.compare = __bt_defcmp; X if (b.prefix == NULL) X b.prefix = __bt_defpfx; X } X X if (b.lorder == 0) X b.lorder = machine_lorder; X } else { X b.compare = __bt_defcmp; X b.cachesize = 0; X b.flags = 0; X b.lorder = machine_lorder; X b.minkeypage = DEFMINKEYPAGE; X b.prefix = __bt_defpfx; X b.psize = 0; X } X X /* Check for the ubiquitous PDP-11. */ X if (b.lorder != BIG_ENDIAN && b.lorder != LITTLE_ENDIAN) X goto einval; X X /* Allocate and initialize DB and BTREE structures. */ X if ((t = malloc(sizeof(BTREE))) == NULL) X goto err; X t->bt_fd = -1; /* Don't close unopened fd on error. */ X if ((t->bt_dbp = dbp = malloc(sizeof(DB))) == NULL) X goto err; X t->bt_bcursor.pgno = P_INVALID; X t->bt_bcursor.index = 0; X t->bt_stack = NULL; X t->bt_sp = t->bt_maxstack = 0; X t->bt_kbuf = t->bt_dbuf = NULL; X t->bt_kbufsz = t->bt_dbufsz = 0; X t->bt_lorder = b.lorder; X t->bt_order = NOT; X t->bt_cmp = b.compare; X t->bt_pfx = b.prefix; X t->bt_flags = 0; X if (t->bt_lorder != machine_lorder) X SET(t, B_NEEDSWAP); X X dbp->type = DB_BTREE; X dbp->internal = t; X dbp->close = __bt_close; X dbp->del = __bt_delete; X dbp->fd = __bt_fd; X dbp->get = __bt_get; X dbp->put = __bt_put; X dbp->seq = __bt_seq; X dbp->sync = __bt_sync; X X /* X * If no file name was supplied, this is an in-memory btree and we X * open a backing temporary file. Otherwise, it's a disk-based tree. X */ X if (fname) { X switch(flags & O_ACCMODE) { X case O_RDONLY: X SET(t, B_RDONLY); X break; X case O_RDWR: X break; X case O_WRONLY: X default: X goto einval; X } X X if ((t->bt_fd = X open(fname, flags & __USE_OPEN_FLAGS, mode)) < 0) X goto err; X X } else { X if ((flags & O_ACCMODE) != O_RDWR) X goto einval; X if ((t->bt_fd = tmp()) == -1) X goto err; X SET(t, B_INMEM); X } X X if (fcntl(t->bt_fd, F_SETFD, 1) == -1) X goto err; X X if (fstat(t->bt_fd, &sb)) X goto err; X if (sb.st_size) { X nr = read(t->bt_fd, &m, sizeof(BTMETA)); X if (nr < 0) X goto err; X if (nr != sizeof(BTMETA)) X goto eftype; X X /* X * Read in the meta-data. This can change the notion of what X * the lorder, page size and flags are, and, when the page size X * changes, the cachesize value can change too. If the user X * specified the wrong byte order for an existing database, we X * don't bother to return an error, we just clear the NEEDSWAP X * bit. X */ X if (m.m_magic == BTREEMAGIC) X CLR(t, B_NEEDSWAP); X else { X SET(t, B_NEEDSWAP); X BLSWAP(m.m_magic); X BLSWAP(m.m_version); X BLSWAP(m.m_psize); X BLSWAP(m.m_free); X BLSWAP(m.m_nrecs); X BLSWAP(m.m_flags); X } X if (m.m_magic != BTREEMAGIC || m.m_version != BTREEVERSION) X goto eftype; X if (m.m_psize < MINPSIZE || m.m_psize > MAX_PAGE_OFFSET + 1 || X m.m_psize & sizeof(indx_t) - 1) X goto eftype; X if (m.m_flags & ~SAVEMETA) X goto eftype; X b.psize = m.m_psize; X t->bt_flags |= m.m_flags; X t->bt_free = m.m_free; X t->bt_nrecs = m.m_nrecs; X } else { X /* X * Set the page size to the best value for I/O to this file. X * Don't overflow the page offset type. X */ X if (b.psize == 0) { X b.psize = sb.st_blksize; X if (b.psize < MINPSIZE) X b.psize = MINPSIZE; X if (b.psize > MAX_PAGE_OFFSET + 1) X b.psize = MAX_PAGE_OFFSET + 1; X } X X /* Set flag if duplicates permitted. */ X if (!(b.flags & R_DUP)) X SET(t, B_NODUPS); X X t->bt_free = P_INVALID; X t->bt_nrecs = 0; X SET(t, B_METADIRTY); X } X X t->bt_psize = b.psize; X X /* Set the cache size; must be a multiple of the page size. */ X if (b.cachesize && b.cachesize & b.psize - 1) X b.cachesize += (~b.cachesize & b.psize - 1) + 1; X if (b.cachesize < b.psize * MINCACHE) X b.cachesize = b.psize * MINCACHE; X X /* Calculate number of pages to cache. */ X ncache = (b.cachesize + t->bt_psize - 1) / t->bt_psize; X X /* X * The btree data structure requires that at least two keys can fit on X * a page, but other than that there's no fixed requirement. The user X * specified a minimum number per page, and we translated that into the X * number of bytes a key/data pair can use before being placed on an X * overflow page. This calculation includes the page header, the size X * of the index referencing the leaf item and the size of the leaf item X * structure. Also, don't let the user specify a minkeypage such that X * a key/data pair won't fit even if both key and data are on overflow X * pages. X */ X t->bt_ovflsize = (t->bt_psize - BTDATAOFF) / b.minkeypage - X (sizeof(indx_t) + NBLEAFDBT(0, 0)); X if (t->bt_ovflsize < NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t)) X t->bt_ovflsize = X NBLEAFDBT(NOVFLSIZE, NOVFLSIZE) + sizeof(indx_t); X X /* Initialize the buffer pool. */ X if ((t->bt_mp = X mpool_open(NULL, t->bt_fd, t->bt_psize, ncache)) == NULL) X goto err; X if (!ISSET(t, B_INMEM)) X mpool_filter(t->bt_mp, __bt_pgin, __bt_pgout, t); X X /* Create a root page if new tree. */ X if (nroot(t) == RET_ERROR) X goto err; X X return (dbp); X Xeinval: errno = EINVAL; X goto err; X Xeftype: errno = EFTYPE; X goto err; X Xerr: if (t) { X if (t->bt_dbp) X free(t->bt_dbp); X if (t->bt_fd != -1) X (void)close(t->bt_fd); X free(t); X } X return (NULL); X} X X/* X * NROOT -- Create the root of a new tree. X * X * Parameters: X * t: tree X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xstatic int Xnroot(t) X BTREE *t; X{ X PAGE *meta, *root; X pgno_t npg; X X if ((meta = mpool_get(t->bt_mp, 0, 0)) != NULL) { X mpool_put(t->bt_mp, meta, 0); X return (RET_SUCCESS); X } X if (errno != EINVAL) X return (RET_ERROR); X X if ((meta = mpool_new(t->bt_mp, &npg)) == NULL) X return (RET_ERROR); X X if ((root = mpool_new(t->bt_mp, &npg)) == NULL) X return (RET_ERROR); X X if (npg != P_ROOT) X return (RET_ERROR); X root->pgno = npg; X root->prevpg = root->nextpg = P_INVALID; X root->lower = BTDATAOFF; X root->upper = t->bt_psize; X root->flags = P_BLEAF; X memset(meta, 0, t->bt_psize); X mpool_put(t->bt_mp, meta, MPOOL_DIRTY); X mpool_put(t->bt_mp, root, MPOOL_DIRTY); X return (RET_SUCCESS); X} X Xstatic int Xtmp() X{ X sigset_t set, oset; X int fd; X char *envtmp; X char path[MAXPATHLEN]; X X envtmp = getenv("TMPDIR"); X (void)snprintf(path, X sizeof(path), "%s/bt.XXXXXX", envtmp ? envtmp : "/tmp"); X X (void)sigfillset(&set); X (void)sigprocmask(SIG_BLOCK, &set, &oset); X if ((fd = mkstemp(path)) != -1) X (void)unlink(path); X (void)sigprocmask(SIG_SETMASK, &oset, NULL); X return(fd); X} X Xstatic int Xbyteorder() X{ X u_long x; /* XXX: 32-bit assumption. */ X u_char *p; X X x = 0x01020304; X p = (u_char *)&x; X switch (*p) { X case 1: X return (BIG_ENDIAN); X case 4: X return (LITTLE_ENDIAN); X default: X return (0); X } X} X Xint X__bt_fd(dbp) X const DB *dbp; X{ X BTREE *t; X X t = dbp->internal; X X if (ISSET(t, B_INMEM)) { X errno = ENOENT; X return (-1); X } X return (t->bt_fd); X} END_OF_FILE if test 10894 -ne `wc -c <'btree/bt_open.c'`; then echo shar: \"'btree/bt_open.c'\" unpacked with wrong size! fi # end of 'btree/bt_open.c' fi if test -f 'btree/bt_put.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_put.c'\" else echo shar: Extracting \"'btree/bt_put.c'\" $8268 characters$ sed "s/^X//" >'btree/bt_put.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_put.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include <sys/types.h> X X#include <errno.h> X#include <stdio.h> X#include <stdlib.h> X#include <string.h> X X#include <db.h> X#include "btree.h" X Xstatic EPG *bt_fast __P((BTREE *, const DBT *, const DBT *, int *)); X X/* X * __BT_PUT -- Add a btree item to the tree. X * X * Parameters: X * dbp: pointer to access method X * key: key X * data: data X * flag: R_NOOVERWRITE X * X * Returns: X * RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key is already in the X * tree and R_NOOVERWRITE specified. X */ Xint X__bt_put(dbp, key, data, flags) X const DB *dbp; X DBT *key; X const DBT *data; X u_int flags; X{ X BTREE *t; X DBT tkey, tdata; X EPG *e; X PAGE *h; X indx_t index, nxtindex; X pgno_t pg; X size_t nbytes; X int dflags, exact, status; X char *dest, db[NOVFLSIZE], kb[NOVFLSIZE]; X X t = dbp->internal; X X switch (flags) { X case R_CURSOR: X if (!ISSET(t, B_SEQINIT)) X goto einval; X if (ISSET(t, B_DELCRSR)) X goto einval; X break; X case 0: X case R_NOOVERWRITE: X break; X default: Xeinval: errno = EINVAL; X return (RET_ERROR); X } X X if (ISSET(t, B_RDONLY)) { X errno = EPERM; X return (RET_ERROR); X } X X /* X * If the key/data won't fit on a page, store it on indirect pages. X * Only store the key on the overflow page if it's too big after the X * data is on an overflow page. X * X * XXX X * If the insert fails later on, these pages aren't recovered. X */ X dflags = 0; X if (key->size + data->size > t->bt_ovflsize) { X if (key->size > t->bt_ovflsize) { Xstorekey: if (__ovfl_put(t, key, &pg) == RET_ERROR) X return (RET_ERROR); X tkey.data = kb; X tkey.size = NOVFLSIZE; X memmove(kb, &pg, sizeof(pgno_t)); X memmove(kb + sizeof(pgno_t), X &key->size, sizeof(size_t)); X dflags |= P_BIGKEY; X key = &tkey; X } X if (key->size + data->size > t->bt_ovflsize) { X if (__ovfl_put(t, data, &pg) == RET_ERROR) X return (RET_ERROR); X tdata.data = db; X tdata.size = NOVFLSIZE; X memmove(db, &pg, sizeof(pgno_t)); X memmove(db + sizeof(pgno_t), X &data->size, sizeof(size_t)); X dflags |= P_BIGDATA; X data = &tdata; X } X if (key->size + data->size > t->bt_ovflsize) X goto storekey; X } X X /* Replace the cursor. */ X if (flags == R_CURSOR) { X if ((h = mpool_get(t->bt_mp, t->bt_bcursor.pgno, 0)) == NULL) X return (RET_ERROR); X index = t->bt_bcursor.index; X goto delete; X } X X /* X * Find the key to delete, or, the location at which to insert. Bt_fast X * and __bt_search pin the returned page. X */ X if (t->bt_order == NOT || (e = bt_fast(t, key, data, &exact)) == NULL) X if ((e = __bt_search(t, key, &exact)) == NULL) X return (RET_ERROR); X h = e->page; X index = e->index; X X /* X * Add the specified key/data pair to the tree. If an identical key X * is already in the tree, and R_NOOVERWRITE is set, an error is X * returned. If R_NOOVERWRITE is not set, the key is either added (if X * duplicates are permitted) or an error is returned. X * X * Pages are split as required. X */ X switch (flags) { X case R_NOOVERWRITE: X if (!exact) X break; X /* X * One special case is if the cursor references the record and X * it's been flagged for deletion. Then, we delete the record, X * leaving the cursor there -- this means that the inserted X * record will not be seen in a cursor scan. X */ X if (ISSET(t, B_DELCRSR) && t->bt_bcursor.pgno == h->pgno && X t->bt_bcursor.index == index) { X CLR(t, B_DELCRSR); X goto delete; X } X mpool_put(t->bt_mp, h, 0); X return (RET_SPECIAL); X default: X if (!exact || !ISSET(t, B_NODUPS)) X break; Xdelete: if (__bt_dleaf(t, h, index) == RET_ERROR) { X mpool_put(t->bt_mp, h, 0); X return (RET_ERROR); X } X break; X } X X /* X * If not enough room, or the user has put a ceiling on the number of X * keys permitted in the page, split the page. The split code will X * insert the key and data and unpin the current page. If inserting X * into the offset array, shift the pointers up. X */ X nbytes = NBLEAFDBT(key->size, data->size); X if (h->upper - h->lower < nbytes + sizeof(indx_t)) { X if ((status = __bt_split(t, h, key, X data, dflags, nbytes, index)) != RET_SUCCESS) X return (status); X goto success; X } X X if (index < (nxtindex = NEXTINDEX(h))) X memmove(h->linp + index + 1, h->linp + index, X (nxtindex - index) * sizeof(indx_t)); X h->lower += sizeof(indx_t); X X h->linp[index] = h->upper -= nbytes; X dest = (char *)h + h->upper; X WR_BLEAF(dest, key, data, dflags); X X if (t->bt_order == NOT) X if (h->nextpg == P_INVALID) { X if (index == NEXTINDEX(h) - 1) { X t->bt_order = FORWARD; X t->bt_last.index = index; X t->bt_last.pgno = h->pgno; X } X } else if (h->prevpg == P_INVALID) { X if (index == 0) { X t->bt_order = BACK; X t->bt_last.index = 0; X t->bt_last.pgno = h->pgno; X } X } X X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X Xsuccess: X if (flags == R_SETCURSOR) { X t->bt_bcursor.pgno = e->page->pgno; X t->bt_bcursor.index = e->index; X } X SET(t, B_MODIFIED); X return (RET_SUCCESS); X} X X#ifdef STATISTICS Xu_long bt_cache_hit, bt_cache_miss; X#endif X X/* X * BT_FAST -- Do a quick check for sorted data. X * X * Parameters: X * t: tree X * key: key to insert X * X * Returns: X * EPG for new record or NULL if not found. X */ Xstatic EPG * Xbt_fast(t, key, data, exactp) X BTREE *t; X const DBT *key, *data; X int *exactp; X{ X EPG e; X PAGE *h; X size_t nbytes; X int cmp; X X if ((h = mpool_get(t->bt_mp, t->bt_last.pgno, 0)) == NULL) { X t->bt_order = NOT; X return (NULL); X } X e.page = h; X e.index = t->bt_last.index; X X /* X * If won't fit in this page or have too many keys in this page, have X * to search to get split stack. X */ X nbytes = NBLEAFDBT(key->size, data->size); X if (h->upper - h->lower < nbytes + sizeof(indx_t)) X goto miss; X X if (t->bt_order == FORWARD) { X if (e.page->nextpg != P_INVALID) X goto miss; X if (e.index != NEXTINDEX(h) - 1) X goto miss; X if ((cmp = __bt_cmp(t, key, &e)) < 0) X goto miss; X t->bt_last.index = cmp ? ++e.index : e.index; X } else { X if (e.page->prevpg != P_INVALID) X goto miss; X if (e.index != 0) X goto miss; X if ((cmp = __bt_cmp(t, key, &e)) > 0) X goto miss; X t->bt_last.index = 0; X } X *exactp = cmp == 0; X#ifdef STATISTICS X ++bt_cache_hit; X#endif X return (&e); X Xmiss: X#ifdef STATISTICS X ++bt_cache_miss; X#endif X t->bt_order = NOT; X mpool_put(t->bt_mp, h, 0); X return (NULL); X} END_OF_FILE if test 8268 -ne `wc -c <'btree/bt_put.c'`; then echo shar: \"'btree/bt_put.c'\" unpacked with wrong size! fi # end of 'btree/bt_put.c' fi if test -f 'btree/bt_seq.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'btree/bt_seq.c'\" else echo shar: Extracting \"'btree/bt_seq.c'\" $9520 characters$ sed "s/^X//" >'btree/bt_seq.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_seq.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X#include <sys/types.h> X X#include <errno.h> X#include <stddef.h> X#include <stdio.h> X#include <stdlib.h> X X#include <db.h> X#include "btree.h" X Xstatic int bt_seqadv __P((BTREE *, EPG *, int)); Xstatic int bt_seqset __P((BTREE *, EPG *, DBT *, int)); X X/* X * Sequential scan support. X * X * The tree can be scanned sequentially, starting from either end of the tree X * or from any specific key. A scan request before any scanning is done is X * initialized as starting from the least node. X * X * Each tree has an EPGNO which has the current position of the cursor. The X * cursor has to survive deletions/insertions in the tree without losing its X * position. This is done by noting deletions without doing them, and then X * doing them when the cursor moves (or the tree is closed). X */ X X/* X * __BT_SEQ -- Btree 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__bt_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 int status; X X /* X * If scan unitialized as yet, or starting at a specific record, set X * the scan to a specific key. Both bt_seqset and bt_seqadv pin the X * page the cursor references if they're successful. X */ X t = dbp->internal; X switch(flags) { X case R_NEXT: X case R_PREV: X if (ISSET(t, B_SEQINIT)) { X status = bt_seqadv(t, &e, flags); X break; X } X /* FALLTHROUGH */ X case R_CURSOR: X case R_FIRST: X case R_LAST: X status = bt_seqset(t, &e, key, flags); X break; X default: X errno = EINVAL; X return (RET_ERROR); X } X X if (status == RET_SUCCESS) { X status = __bt_ret(t, &e, key, data); X X /* Update the actual cursor. */ X t->bt_bcursor.pgno = e.page->pgno; X t->bt_bcursor.index = e.index; X mpool_put(t->bt_mp, e.page, 0); X SET(t, B_SEQINIT); X } X return (status); X} X X/* X * BT_SEQSET -- Set the sequential scan to a specific key. X * X * Parameters: X * t: tree X * ep: storage for returned key X * key: key for initial scan position X * flags: R_CURSOR, R_FIRST, R_LAST, R_NEXT, R_PREV X * X * Side effects: X * Pins the page the cursor references. X * X * Returns: X * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. X */ Xstatic int Xbt_seqset(t, ep, key, flags) X BTREE *t; X EPG *ep; X DBT *key; X int flags; X{ X EPG *e; X PAGE *h; X pgno_t pg; X int exact; X X /* X * Delete any already deleted record that we've been saving because X * the cursor pointed to it. Since going to a specific key, should X * delete any logically deleted records so they aren't found. X */ X if (ISSET(t, B_DELCRSR) && __bt_crsrdel(t, &t->bt_bcursor)) X return (RET_ERROR); X X /* X * Find the first, last or specific key in the tree and point the cursor X * at it. The cursor may not be moved until a new key has been found. X */ X switch(flags) { X case R_CURSOR: /* Keyed scan. */ X /* X * Find the first instance of the key or the smallest key which X * is greater than or equal to the specified key. If run out X * of keys, return RET_SPECIAL. X */ X if (key->data == NULL || key->size == 0) { X errno = EINVAL; X return (RET_ERROR); X } X e = __bt_first(t, key, &exact); /* Returns pinned page. */ X if (e == NULL) X return (RET_ERROR); X /* X * If at the end of a page, skip any empty pages and find the X * next entry. X */ X if (e->index == NEXTINDEX(e->page)) { X h = e->page; X do { X pg = h->nextpg; X mpool_put(t->bt_mp, h, 0); X if (pg == P_INVALID) X return (RET_SPECIAL); X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X } while (NEXTINDEX(h) == 0); X e->index = 0; X e->page = h; X } X *ep = *e; X break; X case R_FIRST: /* First record. */ X case R_NEXT: X /* Walk down the left-hand side of the tree. */ X for (pg = P_ROOT;;) { X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X if (h->flags & (P_BLEAF | P_RLEAF)) X break; X pg = GETBINTERNAL(h, 0)->pgno; X mpool_put(t->bt_mp, h, 0); X } X X /* Skip any empty pages. */ X while (NEXTINDEX(h) == 0 && h->nextpg != P_INVALID) { X pg = h->nextpg; X mpool_put(t->bt_mp, h, 0); X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X } X X if (NEXTINDEX(h) == 0) { X mpool_put(t->bt_mp, h, 0); X return (RET_SPECIAL); X } X X ep->page = h; X ep->index = 0; X break; X case R_LAST: /* Last record. */ X case R_PREV: X /* Walk down the right-hand side of the tree. */ X for (pg = P_ROOT;;) { X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X if (h->flags & (P_BLEAF | P_RLEAF)) X break; X pg = GETBINTERNAL(h, NEXTINDEX(h) - 1)->pgno; X mpool_put(t->bt_mp, h, 0); X } X X /* Skip any empty pages. */ X while (NEXTINDEX(h) == 0 && h->prevpg != P_INVALID) { X pg = h->prevpg; X mpool_put(t->bt_mp, h, 0); X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X } X X if (NEXTINDEX(h) == 0) { X mpool_put(t->bt_mp, h, 0); X return (RET_SPECIAL); X } X X ep->page = h; X ep->index = NEXTINDEX(h) - 1; X break; X } X return (RET_SUCCESS); X} X X/* X * BT_SEQADVANCE -- Advance the sequential scan. X * X * Parameters: X * t: tree X * flags: R_NEXT, R_PREV X * X * Side effects: X * Pins the page the new key/data record is on. X * X * Returns: X * RET_ERROR, RET_SUCCESS or RET_SPECIAL if there's no next key. X */ Xstatic int Xbt_seqadv(t, e, flags) X BTREE *t; X EPG *e; X int flags; X{ X EPGNO *c, delc; X PAGE *h; X indx_t index; X pgno_t pg; X X /* Save the current cursor if going to delete it. */ X c = &t->bt_bcursor; X if (ISSET(t, B_DELCRSR)) X delc = *c; X X if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) X return (RET_ERROR); X X /* X * Find the next/previous record in the tree and point the cursor at it. X * The cursor may not be moved until a new key has been found. X */ X index = c->index; X switch(flags) { X case R_NEXT: /* Next record. */ X if (++index == NEXTINDEX(h)) { X do { X pg = h->nextpg; X mpool_put(t->bt_mp, h, 0); X if (pg == P_INVALID) X return (RET_SPECIAL); X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X } while (NEXTINDEX(h) == 0); X index = 0; X } X break; X case R_PREV: /* Previous record. */ X if (index-- == 0) { X do { X pg = h->prevpg; X mpool_put(t->bt_mp, h, 0); X if (pg == P_INVALID) X return (RET_SPECIAL); X if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL) X return (RET_ERROR); X } while (NEXTINDEX(h) == 0); X index = NEXTINDEX(h) - 1; X } X break; X } X X e->page = h; X e->index = index; X X /* X * Delete any already deleted record that we've been saving because the X * cursor pointed to it. This could cause the new index to be shifted X * down by one if the record we're deleting is on the same page and has X * a larger index. X */ X if (ISSET(t, B_DELCRSR)) { X CLR(t, B_DELCRSR); /* Don't try twice. */ X if (c->pgno == delc.pgno && c->index > delc.index) X --c->index; X if (__bt_crsrdel(t, &delc)) X return (RET_ERROR); X } X return (RET_SUCCESS); X} X X/* X * __BT_CRSRDEL -- Delete the record referenced by the cursor. X * X * Parameters: X * t: tree X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xint X__bt_crsrdel(t, c) X BTREE *t; X EPGNO *c; X{ X PAGE *h; X int status; X X CLR(t, B_DELCRSR); /* Don't try twice. */ X if ((h = mpool_get(t->bt_mp, c->pgno, 0)) == NULL) X return (RET_ERROR); X status = __bt_dleaf(t, h, c->index); X mpool_put(t->bt_mp, h, MPOOL_DIRTY); X return (status); X} END_OF_FILE if test 9520 -ne `wc -c <'btree/bt_seq.c'`; then echo shar: \"'btree/bt_seq.c'\" unpacked with wrong size! fi # end of 'btree/bt_seq.c' fi if test -f 'doc/hash.3.ps' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'doc/hash.3.ps'\" else echo shar: Extracting \"'doc/hash.3.ps'\" $11062 characters$ sed "s/^X//" >'doc/hash.3.ps' <<'END_OF_FILE' X%!PS-Adobe-3.0 X%%Creator: groff version 1.08 X%%DocumentNeededResources: font Times-Roman X%%+ font Times-Bold X%%+ font Times-Italic X%%DocumentSuppliedResources: procset grops 1.08 0 X%%Pages: 2 X%%PageOrder: Ascend X%%Orientation: Portrait X%%EndComments X%%BeginProlog X%%BeginResource: procset grops 1.08 0 X/setpacking where{ Xpop Xcurrentpacking Xtrue setpacking X}if X/grops 120 dict dup begin X/SC 32 def X/A/show load def X/B{0 SC 3 -1 roll widthshow}bind def X/C{0 exch ashow}bind def X/D{0 exch 0 SC 5 2 roll awidthshow}bind def X/E{0 rmoveto show}bind def X/F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def X/G{0 rmoveto 0 exch ashow}bind def X/H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/I{0 exch rmoveto show}bind def X/J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def X/K{0 exch rmoveto 0 exch ashow}bind def X/L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/M{rmoveto show}bind def X/N{rmoveto 0 SC 3 -1 roll widthshow}bind def X/O{rmoveto 0 exch ashow}bind def X/P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/Q{moveto show}bind def X/R{moveto 0 SC 3 -1 roll widthshow}bind def X/S{moveto 0 exch ashow}bind def X/T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/SF{ Xfindfont exch X[exch dup 0 exch 0 exch neg 0 0]makefont Xdup setfont X[exch/setfont cvx]cvx bind def X}bind def X/MF{ Xfindfont X[5 2 roll X0 3 1 roll Xneg 0 0]makefont Xdup setfont X[exch/setfont cvx]cvx bind def X}bind def X/level0 0 def X/RES 0 def X/PL 0 def X/LS 0 def X/PLG{ Xgsave newpath clippath pathbbox grestore Xexch pop add exch pop X}bind def X/BP{ X/level0 save def X1 setlinecap X1 setlinejoin X72 RES div dup scale XLS{ X90 rotate X}{ X0 PL translate X}ifelse X1 -1 scale X}bind def X/EP{ Xlevel0 restore Xshowpage X}bind def X/DA{ Xnewpath arcn stroke X}bind def X/SN{ Xtransform X.25 sub exch .25 sub exch Xround .25 add exch round .25 add exch Xitransform X}bind def X/DL{ XSN Xmoveto XSN Xlineto stroke X}bind def X/DC{ Xnewpath 0 360 arc closepath X}bind def X/TM matrix def X/DE{ XTM currentmatrix pop Xtranslate scale newpath 0 0 .5 0 360 arc closepath XTM setmatrix X}bind def X/RC/rcurveto load def X/RL/rlineto load def X/ST/stroke load def X/MT/moveto load def X/CL/closepath load def X/FL{ Xcurrentgray exch setgray fill setgray X}bind def X/BL/fill load def X/LW/setlinewidth load def X/RE{ Xfindfont Xdup maxlength 1 index/FontName known not{1 add}if dict begin X{ X1 index/FID ne{def}{pop pop}ifelse X}forall X/Encoding exch def Xdup/FontName exch def Xcurrentdict end definefont pop X}bind def X/DEFS 0 def X/EBEGIN{ Xmoveto XDEFS begin X}bind def X/EEND/end load def X/CNT 0 def X/level1 0 def X/PBEGIN{ X/level1 save def Xtranslate Xdiv 3 1 roll div exch scale Xneg exch neg exch translate X0 setgray X0 setlinecap X1 setlinewidth X0 setlinejoin X10 setmiterlimit X[]0 setdash X/setstrokeadjust where{ Xpop Xfalse setstrokeadjust X}if X/setoverprint where{ Xpop Xfalse setoverprint X}if Xnewpath X/CNT countdictstack def Xuserdict begin X/showpage{}def X}bind def X/PEND{ Xclear Xcountdictstack CNT sub{end}repeat Xlevel1 restore X}bind def Xend def X/setpacking where{ Xpop Xsetpacking X}if X%%EndResource X%%IncludeResource: font Times-Roman X%%IncludeResource: font Times-Bold X%%IncludeResource: font Times-Italic Xgrops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72 def/PL X792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron/scaron/zcaron X/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef/.notdef/.notdef X/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef X/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/space X/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright/parenleft X/parenright/asterisk/plus/comma/hyphen/period/slash/zero/one/two/three/four X/five/six/seven/eight/nine/colon/semicolon/less/equal/greater/question/at/A/B/C X/D/E/F/G/H/I/J/K/L/M/N/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash X/bracketright/circumflex/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q X/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase X/guillemotleft/guillemotright/bullet/florin/fraction/perthousand/dagger X/daggerdbl/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut X/dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash X/quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen/brokenbar X/section/dieresis/copyright/ordfeminine/guilsinglleft/logicalnot/minus X/registered/macron/degree/plusminus/twosuperior/threesuperior/acute/mu X/paragraph/periodcentered/cedilla/onesuperior/ordmasculine/guilsinglright X/onequarter/onehalf/threequarters/questiondown/Agrave/Aacute/Acircumflex/Atilde X/Adieresis/Aring/AE/Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute X/Icircumflex/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis X/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn/germandbls X/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla/egrave/eacute X/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis/eth/ntilde/ograve X/oacute/ocircumflex/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex X/udieresis/yacute/thorn/ydieresis]def/Times-Italic@0 ENC0/Times-Italic RE X/Times-Bold@0 ENC0/Times-Bold RE/Times-Roman@0 ENC0/Times-Roman RE X%%EndProlog X%%Page: 1 1 X%%BeginPageSetup XBP X%%EndPageSetup X/F0 10/Times-Roman@0 SF 182.62(HASH$3$ 1993 HASH$3$)72 48 R/F1 9 X/Times-Bold@0 SF -.18(NA)72 84 S(ME).18 E F0 X(hash \255 hash database access method)108 96 Q F1(SYNOPSIS)72 112.8 Q/F2 10 X/Times-Bold@0 SF(#include <sys/types.h>)108 124.8 Q(#include <db)108 136.8 Q X(.h>)-.4 E F1(DESCRIPTION)72 153.6 Q F0 .29(The routine)108 165.6 R/F3 10 X/Times-Italic@0 SF(dbopen)2.79 E F0 .29(is the library interf)2.79 F .29 X(ace to database \214les.)-.1 F .29 X(One of the supported \214le formats is hash \214les.)5.29 F .974 X(The general description of the database access methods is in)108 177.6 R F3 X(dbopen)3.475 E F0 .975($3$, this manual page describes only).24 F X(the hash speci\214c information.)108 189.6 Q(The hash data structure is an e) X108 206.4 Q(xtensible, dynamic hashing scheme.)-.15 E .83 X(The access method speci\214c data structure pro)108 223.2 R .83(vided to)-.15 XF F3(dbopen)3.33 E F0 .83(is de\214ned in the <db)3.33 F .83 X(.h> include \214le as fol-)-.4 F(lo)108 235.2 Q(ws:)-.25 E(typedef struct {) X108 259.2 Q(int bsize;)144 271.2 Q(int cachesize;)144 283.2 Q(int f)144 295.2 Q X-.1(fa)-.25 G(ctor;).1 E(u_long $*hash$$const v)144 307.2 Q X(oid *, size_t$;)-.2 E(int lorder;)144 319.2 Q(int nelem;)144 331.2 Q 2.5(}H) X108 343.2 S(ASHINFO;)122.52 343.2 Q X(The elements of this structure are as follo)108 360 Q(ws:)-.25 E(bsize)108 X376.8 Q F3(Bsize)144 376.8 Q F0 1.393(de\214nes the hash table b)3.893 F(uck) X-.2 E 1.393(et size, and is, by def)-.1 F 1.394(ault, 256 bytes.)-.1 F 1.394 X(It may be preferable to)6.394 F X(increase the page size for disk-resident tables and tables with lar)144 388.8 XQ(ge data items.)-.18 E(cachesize)108 405.6 Q 3.16(As)144 417.6 S .66 X(uggested maximum size, in bytes, of the memory cache.)158.27 417.6 R .659 X(This v)5.659 F .659(alue is)-.25 F F2(only)3.159 E F0(advisory)3.159 E 3.159 X(,a)-.65 G .659(nd the)514.621 417.6 R X(access method will allocate more memory rather than f)144 429.6 Q(ail.)-.1 E X-2.1 -.25(ff a)108 446.4 T(ctor).25 E F3(Ffactor)9.7 E F0 .482 X(indicates a desired density within the hash table.)2.981 F .482 X(It is an approximation of the number of)5.482 F -.1(ke)144 458.4 S .429 X(ys allo)-.05 F .429(wed to accumulate in an)-.25 F 2.929(yo)-.15 G .429(ne b) X291.454 458.4 R(uck)-.2 E .429(et, determining when the hash table gro)-.1 F X.428(ws or shrinks.)-.25 F(The def)144 470.4 Q(ault v)-.1 E(alue is 8.)-.25 E X(hash)108 487.2 Q F3(Hash)144 487.2 Q F0 .1(is a user de\214ned hash function.) X2.6 F .1(Since no hash function performs equally well on all possible)5.1 F X.924(data, the user may \214nd that the b)144 499.2 R .923 X(uilt-in hash function does poorly on a particular data set.)-.2 F(User)5.923 E X1.408(speci\214ed hash functions must tak)144 511.2 R 3.909(et)-.1 G 1.609 -.1 X(wo a)293.431 511.2 T -.18(rg).1 G 1.409 X(uments $a pointer to a byte string and a length$ and).18 F X(return an u_long to be used as the hash v)144 523.2 Q(alue.)-.25 E 9.62 X(lorder The)108 540 R 1.597(byte order for inte)4.097 F 1.596 X(gers in the stored database metadata.)-.15 F 1.596 X(The number should represent the)6.596 F .688(order as an inte)144 552 R .689 X(ger; for e)-.15 F .689(xample, big endian order w)-.15 F .689 X(ould be the number 4,321.)-.1 F(If)5.689 E F3(lor)3.189 E(der)-.37 E F0 .689 X(is 0 $no)3.189 F .822(order is speci\214ed$ the current host order is used.) X144 564 R .822(If the)5.822 F .822(\214le already e)5.822 F .821 X(xists, the speci\214ed v)-.15 F .821(alue is)-.25 F(ignored and the v)144 576 XQ(alue speci\214ed when the tree w)-.25 E(as created is used.)-.1 E(nelem)108 X592.8 Q F3(Nelem)144 592.8 Q F0 .701 X(is an estimate of the \214nal size of the hash table.)3.2 F .701 X(If not set or set too lo)5.701 F 2.001 -.65(w, h)-.25 H .701(ash tables will) X.65 F -.15(ex)144 604.8 S .448(pand gracefully as k).15 F -.15(ey)-.1 G 2.948 X(sa).15 G .448(re entered, although a slight performance de)255.912 604.8 R X.447(gradation may be noticed.)-.15 F(The def)144 616.8 Q(ault v)-.1 E X(alue is 1.)-.25 E .79(If the \214le already e)108 633.6 R .79 X(xists $and the O_TR)-.15 F .79(UNC \215ag is not speci\214ed$, the v)-.4 F X.79(alues speci\214ed for the parameters)-.25 F(bsize, f)108 645.6 Q -.1(fa) X-.25 G(ctor).1 E 2.5(,l)-.4 G(order and nelem are ignored and the v)167.23 X645.6 Q(alues speci\214ed when the tree w)-.25 E(as created are used.)-.1 E X1.232(If a hash function is speci\214ed,)108 662.4 R F3(hash_open)3.731 E F0 X1.231(will attempt to determine if the hash function speci\214ed is the)3.731 F X(same as the one with which the database w)108 674.4 Q(as created, and will f) X-.1 E(ail if it is not.)-.1 E(Backw)108 691.2 Q .861(ard compatible interf)-.1 XF .861(aces to the routines described in)-.1 F F3(dbm)3.362 E F0 .862 X($3$, and).32 F F3(ndbm)3.362 E F0 .862($3$ are pro).32 F .862(vided, ho) X-.15 F(we)-.25 E -.15(ve)-.25 G -.4(r,).15 G(these interf)108 703.2 Q X(aces are not compatible with pre)-.1 E(vious \214le formats.)-.25 E 214.835 X(6, June)72 768 R(1)535 768 Q EP X%%Page: 2 2 X%%BeginPageSetup XBP X%%EndPageSetup X/F0 10/Times-Roman@0 SF 182.62(HASH$3$ 1993 HASH$3$)72 48 R/F1 9 X/Times-Bold@0 SF(SEE ALSO)72 84 Q/F2 10/Times-Italic@0 SF(btr)108 96 Q(ee)-.37 XE F0($3$,).18 E F2(dbopen)2.5 E F0($3$,).24 E F2(mpool)2.5 E F0($3$,).51 XE F2 -.37(re)2.5 G(cno).37 E F0($3$).18 E F2(Dynamic Hash T)108 108 Q(ables) X-.92 E F0 2.5(,P).27 G(er)206.79 108 Q(-Ak)-.2 E 2.5(eL)-.1 G X(arson, Communications of the A)242.86 108 Q(CM, April 1988.)-.4 E F2 2.5(AN) X108 120 S .3 -.15(ew H)123.28 120 T(ash P).15 E(ac)-.8 E(ka)-.2 E .2 -.1(ge f) X-.1 H(or UNIX).1 E F0 2.5(,M).94 G(ar)248.41 120 Q(go Seltzer)-.18 E 2.5(,U)-.4 XG(SENIX Proceedings, W)308.09 120 Q(inter 1991.)-.4 E F1 -.09(BU)72 136.8 S(GS) X.09 E F0(Only big and little endian byte order is supported.)108 148.8 Q X214.835(6, June)72 768 R(2)535 768 Q EP X%%Trailer Xend X%%EOF END_OF_FILE if test 11062 -ne `wc -c <'doc/hash.3.ps'`; then echo shar: \"'doc/hash.3.ps'\" unpacked with wrong size! fi # end of 'doc/hash.3.ps' fi if test -f 'hash/hash.h' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'hash/hash.h'\" else echo shar: Extracting \"'hash/hash.h'\" $9978 characters$ sed "s/^X//" >'hash/hash.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 * @(#)hash.h 8.1 (Berkeley) 6/4/93 X */ X X/* Operations */ Xtypedef enum { X HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT X} ACTION; X X/* Buffer Management structures */ Xtypedef struct _bufhead BUFHEAD; X Xstruct _bufhead { X BUFHEAD *prev; /* LRU links */ X BUFHEAD *next; /* LRU links */ X BUFHEAD *ovfl; /* Overflow page buffer header */ X u_int addr; /* Address of this page */ X char *page; /* Actual page data */ X char flags; X#define BUF_MOD 0x0001 X#define BUF_DISK 0x0002 X#define BUF_BUCKET 0x0004 X#define BUF_PIN 0x0008 X}; X X#define IS_BUCKET(X) ((X) & BUF_BUCKET) X Xtypedef BUFHEAD **SEGMENT; X X/* Hash Table Information */ Xtypedef struct hashhdr { /* Disk resident portion */ X int magic; /* Magic NO for hash tables */ X int version; /* Version ID */ X long lorder; /* Byte Order */ X int bsize; /* Bucket/Page Size */ X int bshift; /* Bucket shift */ X int dsize; /* Directory Size */ X int ssize; /* Segment Size */ X int sshift; /* Segment shift */ X int ovfl_point; /* Where overflow pages are being allocated */ X int last_freed; /* Last overflow page freed */ X int max_bucket; /* ID of Maximum bucket in use */ X int high_mask; /* Mask to modulo into entire table */ X int low_mask; /* Mask to modulo into lower half of table */ X int ffactor; /* Fill factor */ X int nkeys; /* Number of keys in hash table */ X int hdrpages; /* Size of table header */ X int h_charkey; /* value of hash(CHARKEY) */ X#define NCACHED 32 /* number of bit maps and spare points */ X int spares[NCACHED];/* spare pages for overflow */ X u_short bitmaps[NCACHED]; /* address of overflow page bitmaps */ X} HASHHDR; X Xtypedef struct htab { /* Memory resident data structure */ X HASHHDR hdr; /* Header */ X int nsegs; /* Number of allocated segments */ X int exsegs; /* Number of extra allocated segments */ X int (*hash) (); /* Hash Function */ X int flags; /* Flag values */ X int fp; /* File pointer */ X char *tmp_buf; /* Temporary Buffer for BIG data */ X char *tmp_key; /* Temporary Buffer for BIG keys */ X BUFHEAD *cpage; /* Current page */ X int cbucket; /* Current bucket */ X int cndx; /* Index of next item on cpage */ X int errno; /* Error Number -- for DBM compatability */ X int new_file; /* Indicates if fd is backing store or no */ X int save_file; /* Indicates whether we need to flush file at X * exit */ X u_long *mapp[NCACHED]; /* Pointers to page maps */ X int nmaps; /* Initial number of bitmaps */ X int nbufs; /* Number of buffers left to allocate */ X BUFHEAD bufhead; /* Header of buffer lru list */ X SEGMENT *dir; /* Hash Bucket directory */ X} HTAB; X X/* X * Constants X */ X#define MAX_BSIZE 65536 /* 2^16 */ X#define MIN_BUFFERS 6 X#define MINHDRSIZE 512 X#define DEF_BUFSIZE 65536 /* 64 K */ X#define DEF_BUCKET_SIZE 4096 X#define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ X#define DEF_SEGSIZE 256 X#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ X#define DEF_DIRSIZE 256 X#define DEF_FFACTOR 65536 X#define MIN_FFACTOR 4 X#define SPLTMAX 8 X#define CHARKEY "%$sniglet^&" X#define NUMKEY 1038583 X#define BYTE_SHIFT 3 X#define INT_TO_BYTE 2 X#define INT_BYTE_SHIFT 5 X#define ALL_SET ((u_int)0xFFFFFFFF) X#define ALL_CLEAR 0 X X#define PTROF(X) ((BUFHEAD *)((u_int)(X)&~0x3)) X#define ISMOD(X) ((u_int)(X)&0x1) X#define DOMOD(X) ((X) = (char *)((u_int)(X)|0x1)) X#define ISDISK(X) ((u_int)(X)&0x2) X#define DODISK(X) ((X) = (char *)((u_int)(X)|0x2)) X X#define BITS_PER_MAP 32 X X/* Given the address of the beginning of a big map, clear/set the nth bit */ X#define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) X#define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) X#define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) X X/* Overflow management */ X/* X * Overflow page numbers are allocated per split point. At each doubling of X * the table, we can allocate extra pages. So, an overflow page number has X * the top 5 bits indicate which split point and the lower 11 bits indicate X * which page at that split point is indicated (pages within split points are X * numberered starting with 1). X */ X X#define SPLITSHIFT 11 X#define SPLITMASK 0x7FF X#define SPLITNUM(N) (((u_int)(N)) >> SPLITSHIFT) X#define OPAGENUM(N) ((N) & SPLITMASK) X#define OADDR_OF(S,O) ((u_int)((u_int)(S) << SPLITSHIFT) + (O)) X X#define BUCKET_TO_PAGE(B) \ X (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0) X#define OADDR_TO_PAGE(B) \ X BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)); X X/* X * page.h contains a detailed description of the page format. X * X * Normally, keys and data are accessed from offset tables in the top of X * each page which point to the beginning of the key and data. There are X * four flag values which may be stored in these offset tables which indicate X * the following: X * X * X * OVFLPAGE Rather than a key data pair, this pair contains X * the address of an overflow page. The format of X * the pair is: X * OVERFLOW_PAGE_NUMBER OVFLPAGE X * X * PARTIAL_KEY This must be the first key/data pair on a page X * and implies that page contains only a partial key. X * That is, the key is too big to fit on a single page X * so it starts on this page and continues on the next. X * The format of the page is: X * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE X * X * KEY_OFF -- offset of the beginning of the key X * PARTIAL_KEY -- 1 X * OVFL_PAGENO - page number of the next overflow page X * OVFLPAGE -- 0 X * X * FULL_KEY This must be the first key/data pair on the page. It X * is used in two cases. X * X * Case 1: X * There is a complete key on the page but no data X * (because it wouldn't fit). The next page contains X * the data. X * X * Page format it: X * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE X * X * KEY_OFF -- offset of the beginning of the key X * FULL_KEY -- 2 X * OVFL_PAGENO - page number of the next overflow page X * OVFLPAGE -- 0 X * X * Case 2: X * This page contains no key, but part of a large X * data field, which is continued on the next page. X * X * Page format it: X * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE X * X * KEY_OFF -- offset of the beginning of the data on X * this page X * FULL_KEY -- 2 X * OVFL_PAGENO - page number of the next overflow page X * OVFLPAGE -- 0 X * X * FULL_KEY_DATA X * This must be the first key/data pair on the page. X * There are two cases: X * X * Case 1: X * This page contains a key and the beginning of the X * data field, but the data field is continued on the X * next page. X * X * Page format is: X * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF X * X * KEY_OFF -- offset of the beginning of the key X * FULL_KEY_DATA -- 3 X * OVFL_PAGENO - page number of the next overflow page X * DATA_OFF -- offset of the beginning of the data X * X * Case 2: X * This page contains the last page of a big data pair. X * There is no key, only the tail end of the data X * on this page. X * X * Page format is: X * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE> X * X * DATA_OFF -- offset of the beginning of the data on X * this page X * FULL_KEY_DATA -- 3 X * OVFL_PAGENO - page number of the next overflow page X * OVFLPAGE -- 0 X * X * OVFL_PAGENO and OVFLPAGE are optional (they are X * not present if there is no next page). X */ X X#define OVFLPAGE 0 X#define PARTIAL_KEY 1 X#define FULL_KEY 2 X#define FULL_KEY_DATA 3 X#define REAL_KEY 4 X X/* Short hands for accessing structure */ X#define BSIZE hdr.bsize X#define BSHIFT hdr.bshift X#define DSIZE hdr.dsize X#define SGSIZE hdr.ssize X#define SSHIFT hdr.sshift X#define LORDER hdr.lorder X#define OVFL_POINT hdr.ovfl_point X#define LAST_FREED hdr.last_freed X#define MAX_BUCKET hdr.max_bucket X#define FFACTOR hdr.ffactor X#define HIGH_MASK hdr.high_mask X#define LOW_MASK hdr.low_mask X#define NKEYS hdr.nkeys X#define HDRPAGES hdr.hdrpages X#define SPARES hdr.spares X#define BITMAPS hdr.bitmaps X#define VERSION hdr.version X#define MAGIC hdr.magic X#define NEXT_FREE hdr.next_free X#define H_CHARKEY hdr.h_charkey END_OF_FILE if test 9978 -ne `wc -c <'hash/hash.h'`; then echo shar: \"'hash/hash.h'\" unpacked with wrong size! fi # end of 'hash/hash.h' fi if test -f 'hash/hash_buf.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'hash/hash_buf.c'\" else echo shar: Extracting \"'hash/hash_buf.c'\" $9015 characters$ sed "s/^X//" >'hash/hash_buf.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_buf.c 8.1 (Berkeley) 6/4/93"; X#endif /* LIBC_SCCS and not lint */ X X/* X * PACKAGE: hash X * X * DESCRIPTION: X * Contains buffer management X * X * ROUTINES: X * External X * __buf_init X * __get_buf X * __buf_free X * __reclaim_buf X * Internal X * newbuf X */ X X#include <sys/param.h> X X#include <errno.h> X#include <stdio.h> X#include <stdlib.h> X#ifdef DEBUG X#include <assert.h> X#endif X X#include <db.h> X#include "hash.h" X#include "page.h" X#include "extern.h" X Xstatic BUFHEAD *newbuf __P((HTAB *, u_int, BUFHEAD *)); X X/* Unlink B from its place in the lru */ X#define BUF_REMOVE(B) { \ X (B)->prev->next = (B)->next; \ X (B)->next->prev = (B)->prev; \ X} X X/* Insert B after P */ X#define BUF_INSERT(B, P) { \ X (B)->next = (P)->next; \ X (B)->prev = (P); \ X (P)->next = (B); \ X (B)->next->prev = (B); \ X} X X#define MRU hashp->bufhead.next X#define LRU hashp->bufhead.prev X X#define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead) X#define LRU_INSERT(B) BUF_INSERT((B), LRU) X X/* X * We are looking for a buffer with address "addr". If prev_bp is NULL, then X * address is a bucket index. If prev_bp is not NULL, then it points to the X * page previous to an overflow page that we are trying to find. X * X * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer X * be valid. Therefore, you must always verify that its address matches the X * address you are seeking. X */ Xextern BUFHEAD * X__get_buf(hashp, addr, prev_bp, newpage) X HTAB *hashp; X u_int addr; X BUFHEAD *prev_bp; X int newpage; /* If prev_bp set, indicates a new overflow page. */ X{ X register BUFHEAD *bp; X register u_int is_disk_mask; X register int is_disk, segment_ndx; X SEGMENT segp; X X is_disk = 0; X is_disk_mask = 0; X if (prev_bp) { X bp = prev_bp->ovfl; X if (!bp || (bp->addr != addr)) X bp = NULL; X if (!newpage) X is_disk = BUF_DISK; X } else { X /* Grab buffer out of directory */ X segment_ndx = addr & (hashp->SGSIZE - 1); X X /* valid segment ensured by __call_hash() */ X segp = hashp->dir[addr >> hashp->SSHIFT]; X#ifdef DEBUG X assert(segp != NULL); X#endif X bp = PTROF(segp[segment_ndx]); X is_disk_mask = ISDISK(segp[segment_ndx]); X is_disk = is_disk_mask || !hashp->new_file; X } X X if (!bp) { X bp = newbuf(hashp, addr, prev_bp); X if (!bp || X __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0)) X return (NULL); X if (!prev_bp) X segp[segment_ndx] = X (BUFHEAD *)((u_int)bp | is_disk_mask); X } else { X BUF_REMOVE(bp); X MRU_INSERT(bp); X } X return (bp); X} X X/* X * We need a buffer for this page. Either allocate one, or evict a resident X * one (if we have as many buffers as we're allowed) and put this one in. X * X * If newbuf finds an error (returning NULL), it also sets errno. X */ Xstatic BUFHEAD * Xnewbuf(hashp, addr, prev_bp) X HTAB *hashp; X u_int addr; X BUFHEAD *prev_bp; X{ X register BUFHEAD *bp; /* The buffer we're going to use */ X register BUFHEAD *xbp; /* Temp pointer */ X register BUFHEAD *next_xbp; X SEGMENT segp; X int segment_ndx; X u_short oaddr, *shortp; X X oaddr = 0; X bp = LRU; X /* X * If LRU buffer is pinned, the buffer pool is too small. We need to X * allocate more buffers. X */ X if (hashp->nbufs || (bp->flags & BUF_PIN)) { X /* Allocate a new one */ X bp = malloc(sizeof(struct _bufhead)); X if (!bp || !(bp->page = malloc(hashp->BSIZE))) X return (NULL); X if (hashp->nbufs) X hashp->nbufs--; X } else { X /* Kick someone out */ X BUF_REMOVE(bp); X /* X * If this is an overflow page with addr 0, it's already been X * flushed back in an overflow chain and initialized. X */ X if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) { X /* X * Set oaddr before __put_page so that you get it X * before bytes are swapped. X */ X shortp = (u_short *)bp->page; X if (shortp[0]) X oaddr = shortp[shortp[0] - 1]; X if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page, X bp->addr, (int)IS_BUCKET(bp->flags), 0)) X return (NULL); X /* X * Update the pointer to this page (i.e. invalidate it). X * X * If this is a new file (i.e. we created it at open X * time), make sure that we mark pages which have been X * written to disk so we retrieve them from disk later, X * rather than allocating new pages. X */ X if (IS_BUCKET(bp->flags)) { X segment_ndx = bp->addr & (hashp->SGSIZE - 1); X segp = hashp->dir[bp->addr >> hashp->SSHIFT]; X#ifdef DEBUG X assert(segp != NULL); X#endif X X if (hashp->new_file && X ((bp->flags & BUF_MOD) || X ISDISK(segp[segment_ndx]))) X segp[segment_ndx] = (BUFHEAD *)BUF_DISK; X else X segp[segment_ndx] = NULL; X } X /* X * Since overflow pages can only be access by means of X * their bucket, free overflow pages associated with X * this bucket. X */ X for (xbp = bp; xbp->ovfl;) { X next_xbp = xbp->ovfl; X xbp->ovfl = 0; X xbp = next_xbp; X X /* Check that ovfl pointer is up date. */ X if (IS_BUCKET(xbp->flags) || X (oaddr != xbp->addr)) X break; X X shortp = (u_short *)xbp->page; X if (shortp[0]) X /* set before __put_page */ X oaddr = shortp[shortp[0] - 1]; X if ((xbp->flags & BUF_MOD) && __put_page(hashp, X xbp->page, xbp->addr, 0, 0)) X return (NULL); X xbp->addr = 0; X xbp->flags = 0; X BUF_REMOVE(xbp); X LRU_INSERT(xbp); X } X } X } X X /* Now assign this buffer */ X bp->addr = addr; X#ifdef DEBUG1 X (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n", X bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0); X#endif X bp->ovfl = NULL; X if (prev_bp) { X /* X * If prev_bp is set, this is an overflow page, hook it in to X * the buffer overflow links. X */ X#ifdef DEBUG1 X (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n", X prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0), X (bp ? bp->addr : 0)); X#endif X prev_bp->ovfl = bp; X bp->flags = 0; X } else X bp->flags = BUF_BUCKET; X MRU_INSERT(bp); X return (bp); X} X Xextern void X__buf_init(hashp, nbytes) X HTAB *hashp; X int nbytes; X{ X BUFHEAD *bfp; X int npages; X X bfp = &(hashp->bufhead); X npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT; X npages = MAX(npages, MIN_BUFFERS); X X hashp->nbufs = npages; X bfp->next = bfp; X bfp->prev = bfp; X /* X * This space is calloc'd so these are already null. X * X * bfp->ovfl = NULL; X * bfp->flags = 0; X * bfp->page = NULL; X * bfp->addr = 0; X */ X} X Xextern int X__buf_free(hashp, do_free, to_disk) X HTAB *hashp; X int do_free, to_disk; X{ X BUFHEAD *bp; X X /* Need to make sure that buffer manager has been initialized */ X if (!LRU) X return (0); X for (bp = LRU; bp != &hashp->bufhead;) { X /* Check that the buffer is valid */ X if (bp->addr || IS_BUCKET(bp->flags)) { X if (to_disk && (bp->flags & BUF_MOD) && X __put_page(hashp, bp->page, X bp->addr, IS_BUCKET(bp->flags), 0)) X return (-1); X } X /* Check if we are freeing stuff */ X if (do_free) { X if (bp->page) X free(bp->page); X BUF_REMOVE(bp); X free(bp); X bp = LRU; X } else X bp = bp->prev; X } X return (0); X} X Xextern void X__reclaim_buf(hashp, bp) X HTAB *hashp; X BUFHEAD *bp; X{ X bp->ovfl = 0; X bp->addr = 0; X bp->flags = 0; X BUF_REMOVE(bp); X LRU_INSERT(bp); X} END_OF_FILE if test 9015 -ne `wc -c <'hash/hash_buf.c'`; then echo shar: \"'hash/hash_buf.c'\" unpacked with wrong size! fi # end of 'hash/hash_buf.c' fi if test -f 'mpool/mpool.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'mpool/mpool.c'\" else echo shar: Extracting \"'mpool/mpool.c'\" $11661 characters$ sed "s/^X//" >'mpool/mpool.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[] = "@(#)mpool.c 8.1 (Berkeley) 6/6/93"; X#endif /* LIBC_SCCS and not lint */ X X#include <sys/param.h> X#include <sys/stat.h> X X#include <errno.h> X#include <stdio.h> X#include <stdlib.h> X#include <string.h> X#include <unistd.h> X X#include <db.h> X#define __MPOOLINTERFACE_PRIVATE X#include "mpool.h" X Xstatic BKT *mpool_bkt __P((MPOOL *)); Xstatic BKT *mpool_look __P((MPOOL *, pgno_t)); Xstatic int mpool_write __P((MPOOL *, BKT *)); X#ifdef DEBUG Xstatic void __mpoolerr __P((const char *fmt, ...)); X#endif X X/* X * MPOOL_OPEN -- initialize a memory pool. X * X * Parameters: X * key: Shared buffer key. X * fd: File descriptor. X * pagesize: File page size. X * maxcache: Max number of cached pages. X * X * Returns: X * MPOOL pointer, NULL on error. X */ XMPOOL * Xmpool_open(key, fd, pagesize, maxcache) X DBT *key; X int fd; X pgno_t pagesize, maxcache; X{ X struct stat sb; X MPOOL *mp; X int entry; X X if (fstat(fd, &sb)) X return (NULL); X /* XXX X * We should only set st_size to 0 for pipes -- 4.4BSD has the fix so X * that stat(2) returns true for ISSOCK on pipes. Until then, this is X * fairly close. X */ X if (!S_ISREG(sb.st_mode)) { X errno = ESPIPE; X return (NULL); X } X X if ((mp = malloc(sizeof(MPOOL))) == NULL) X return (NULL); X mp->free.cnext = mp->free.cprev = (BKT *)&mp->free; X mp->lru.cnext = mp->lru.cprev = (BKT *)&mp->lru; X for (entry = 0; entry < HASHSIZE; ++entry) X mp->hashtable[entry].hnext = mp->hashtable[entry].hprev = X mp->hashtable[entry].cnext = mp->hashtable[entry].cprev = X (BKT *)&mp->hashtable[entry]; X mp->curcache = 0; X mp->maxcache = maxcache; X mp->pagesize = pagesize; X mp->npages = sb.st_size / pagesize; X mp->fd = fd; X mp->pgcookie = NULL; X mp->pgin = mp->pgout = NULL; X X#ifdef STATISTICS X mp->cachehit = mp->cachemiss = mp->pagealloc = mp->pageflush = X mp->pageget = mp->pagenew = mp->pageput = mp->pageread = X mp->pagewrite = 0; X#endif X return (mp); X} X X/* X * MPOOL_FILTER -- initialize input/output filters. X * X * Parameters: X * pgin: Page in conversion routine. X * pgout: Page out conversion routine. X * pgcookie: Cookie for page in/out routines. X */ Xvoid Xmpool_filter(mp, pgin, pgout, pgcookie) X MPOOL *mp; X void (*pgin) __P((void *, pgno_t, void *)); X void (*pgout) __P((void *, pgno_t, void *)); X void *pgcookie; X{ X mp->pgin = pgin; X mp->pgout = pgout; X mp->pgcookie = pgcookie; X} X X/* X * MPOOL_NEW -- get a new page X * X * Parameters: X * mp: mpool cookie X * pgnoadddr: place to store new page number X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xvoid * Xmpool_new(mp, pgnoaddr) X MPOOL *mp; X pgno_t *pgnoaddr; X{ X BKT *b; X BKTHDR *hp; X X#ifdef STATISTICS X ++mp->pagenew; X#endif X /* X * Get a BKT from the cache. Assign a new page number, attach it to X * the hash and lru chains and return. X */ X if ((b = mpool_bkt(mp)) == NULL) X return (NULL); X *pgnoaddr = b->pgno = mp->npages++; X b->flags = MPOOL_PINNED; X inshash(b, b->pgno); X inschain(b, &mp->lru); X return (b->page); X} X X/* X * MPOOL_GET -- get a page from the pool X * X * Parameters: X * mp: mpool cookie X * pgno: page number X * flags: not used X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xvoid * Xmpool_get(mp, pgno, flags) X MPOOL *mp; X pgno_t pgno; X u_int flags; /* XXX not used? */ X{ X BKT *b; X BKTHDR *hp; X off_t off; X int nr; X X /* X * If asking for a specific page that is already in the cache, find X * it and return it. X */ X if (b = mpool_look(mp, pgno)) { X#ifdef STATISTICS X ++mp->pageget; X#endif X#ifdef DEBUG X if (b->flags & MPOOL_PINNED) X __mpoolerr("mpool_get: page %d already pinned", X b->pgno); X#endif X rmchain(b); X inschain(b, &mp->lru); X b->flags |= MPOOL_PINNED; X return (b->page); X } X X /* Not allowed to retrieve a non-existent page. */ X if (pgno >= mp->npages) { X errno = EINVAL; X return (NULL); X } X X /* Get a page from the cache. */ X if ((b = mpool_bkt(mp)) == NULL) X return (NULL); X b->pgno = pgno; X b->flags = MPOOL_PINNED; X X#ifdef STATISTICS X ++mp->pageread; X#endif X /* Read in the contents. */ X off = mp->pagesize * pgno; X if (lseek(mp->fd, off, SEEK_SET) != off) X return (NULL); X if ((nr = read(mp->fd, b->page, mp->pagesize)) != mp->pagesize) { X if (nr >= 0) X errno = EFTYPE; X return (NULL); X } X if (mp->pgin) X (mp->pgin)(mp->pgcookie, b->pgno, b->page); X X inshash(b, b->pgno); X inschain(b, &mp->lru); X#ifdef STATISTICS X ++mp->pageget; X#endif X return (b->page); X} X X/* X * MPOOL_PUT -- return a page to the pool X * X * Parameters: X * mp: mpool cookie X * page: page pointer X * pgno: page number X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xint Xmpool_put(mp, page, flags) X MPOOL *mp; X void *page; X u_int flags; X{ X BKT *baddr; X#ifdef DEBUG X BKT *b; X#endif X X#ifdef STATISTICS X ++mp->pageput; X#endif X baddr = (BKT *)((char *)page - sizeof(BKT)); X#ifdef DEBUG X if (!(baddr->flags & MPOOL_PINNED)) X __mpoolerr("mpool_put: page %d not pinned", b->pgno); X for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) { X if (b == (BKT *)&mp->lru) X __mpoolerr("mpool_put: %0x: bad address", baddr); X if (b == baddr) X break; X } X#endif X baddr->flags &= ~MPOOL_PINNED; X baddr->flags |= flags & MPOOL_DIRTY; X return (RET_SUCCESS); X} X X/* X * MPOOL_CLOSE -- close the buffer pool X * X * Parameters: X * mp: mpool cookie X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xint Xmpool_close(mp) X MPOOL *mp; X{ X BKT *b, *next; X X /* Free up any space allocated to the lru pages. */ X for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = next) { X next = b->cprev; X free(b); X } X free(mp); X return (RET_SUCCESS); X} X X/* X * MPOOL_SYNC -- sync the file to disk. X * X * Parameters: X * mp: mpool cookie X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xint Xmpool_sync(mp) X MPOOL *mp; X{ X BKT *b; X X for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev) X if (b->flags & MPOOL_DIRTY && mpool_write(mp, b) == RET_ERROR) X return (RET_ERROR); X return (fsync(mp->fd) ? RET_ERROR : RET_SUCCESS); X} X X/* X * MPOOL_BKT -- get/create a BKT from the cache X * X * Parameters: X * mp: mpool cookie X * X * Returns: X * NULL on failure and a pointer to the BKT on success X */ Xstatic BKT * Xmpool_bkt(mp) X MPOOL *mp; X{ X BKT *b; X X if (mp->curcache < mp->maxcache) X goto new; X X /* X * If the cache is maxxed out, search the lru list for a buffer we X * can flush. If we find one, write it if necessary and take it off X * any lists. If we don't find anything we grow the cache anyway. X * The cache never shrinks. X */ X for (b = mp->lru.cprev; b != (BKT *)&mp->lru; b = b->cprev) X if (!(b->flags & MPOOL_PINNED)) { X if (b->flags & MPOOL_DIRTY && X mpool_write(mp, b) == RET_ERROR) X return (NULL); X rmhash(b); X rmchain(b); X#ifdef STATISTICS X ++mp->pageflush; X#endif X#ifdef DEBUG X { X void *spage; X spage = b->page; X memset(b, 0xff, sizeof(BKT) + mp->pagesize); X b->page = spage; X } X#endif X return (b); X } X Xnew: if ((b = malloc(sizeof(BKT) + mp->pagesize)) == NULL) X return (NULL); X#ifdef STATISTICS X ++mp->pagealloc; X#endif X#ifdef DEBUG X memset(b, 0xff, sizeof(BKT) + mp->pagesize); X#endif X b->page = (char *)b + sizeof(BKT); X ++mp->curcache; X return (b); X} X X/* X * MPOOL_WRITE -- sync a page to disk X * X * Parameters: X * mp: mpool cookie X * X * Returns: X * RET_ERROR, RET_SUCCESS X */ Xstatic int Xmpool_write(mp, b) X MPOOL *mp; X BKT *b; X{ X off_t off; X X if (mp->pgout) X (mp->pgout)(mp->pgcookie, b->pgno, b->page); X X#ifdef STATISTICS X ++mp->pagewrite; X#endif X off = mp->pagesize * b->pgno; X if (lseek(mp->fd, off, SEEK_SET) != off) X return (RET_ERROR); X if (write(mp->fd, b->page, mp->pagesize) != mp->pagesize) X return (RET_ERROR); X b->flags &= ~MPOOL_DIRTY; X return (RET_SUCCESS); X} X X/* X * MPOOL_LOOK -- lookup a page X * X * Parameters: X * mp: mpool cookie X * pgno: page number X * X * Returns: X * NULL on failure and a pointer to the BKT on success X */ Xstatic BKT * Xmpool_look(mp, pgno) X MPOOL *mp; X pgno_t pgno; X{ X register BKT *b; X register BKTHDR *tb; X X /* XXX X * If find the buffer, put it first on the hash chain so can X * find it again quickly. X */ X tb = &mp->hashtable[HASHKEY(pgno)]; X for (b = tb->hnext; b != (BKT *)tb; b = b->hnext) X if (b->pgno == pgno) { X#ifdef STATISTICS X ++mp->cachehit; X#endif X return (b); X } X#ifdef STATISTICS X ++mp->cachemiss; X#endif X return (NULL); X} X X#ifdef STATISTICS X/* X * MPOOL_STAT -- cache statistics X * X * Parameters: X * mp: mpool cookie X */ Xvoid Xmpool_stat(mp) X MPOOL *mp; X{ X BKT *b; X int cnt; X char *sep; X X (void)fprintf(stderr, "%lu pages in the file\n", mp->npages); X (void)fprintf(stderr, X "page size %lu, cacheing %lu pages of %lu page max cache\n", X mp->pagesize, mp->curcache, mp->maxcache); X (void)fprintf(stderr, "%lu page puts, %lu page gets, %lu page new\n", X mp->pageput, mp->pageget, mp->pagenew); X (void)fprintf(stderr, "%lu page allocs, %lu page flushes\n", X mp->pagealloc, mp->pageflush); X if (mp->cachehit + mp->cachemiss) X (void)fprintf(stderr, X "%.0f%% cache hit rate (%lu hits, %lu misses)\n", X ((double)mp->cachehit / (mp->cachehit + mp->cachemiss)) X * 100, mp->cachehit, mp->cachemiss); X (void)fprintf(stderr, "%lu page reads, %lu page writes\n", X mp->pageread, mp->pagewrite); X X sep = ""; X cnt = 0; X for (b = mp->lru.cnext; b != (BKT *)&mp->lru; b = b->cnext) { X (void)fprintf(stderr, "%s%d", sep, b->pgno); X if (b->flags & MPOOL_DIRTY) X (void)fprintf(stderr, "d"); X if (b->flags & MPOOL_PINNED) X (void)fprintf(stderr, "P"); X if (++cnt == 10) { X sep = "\n"; X cnt = 0; X } else X sep = ", "; X X } X (void)fprintf(stderr, "\n"); X} X#endif X X#ifdef DEBUG X#if __STDC__ X#include <stdarg.h> X#else X#include <varargs.h> X#endif X Xstatic void X#if __STDC__ X__mpoolerr(const char *fmt, ...) X#else X__mpoolerr(fmt, va_alist) X char *fmt; X va_dcl X#endif X{ X va_list ap; X#if __STDC__ X va_start(ap, fmt); X#else X va_start(ap); X#endif X (void)vfprintf(stderr, fmt, ap); X va_end(ap); X (void)fprintf(stderr, "\n"); X abort(); X /* NOTREACHED */ X} X#endif END_OF_FILE if test 11661 -ne `wc -c <'mpool/mpool.c'`; then echo shar: \"'mpool/mpool.c'\" unpacked with wrong size! fi # end of 'mpool/mpool.c' fi echo shar: End of archive 4 $of 9$. cp /dev/null ark4isdone 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