sdbm part 2
Ozan Yigit
oz at nexus.YorkU.CA
Sun Dec 16 02:38:34 AEST 1990
#! /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 2 (of 2)."
# Contents: dist/readme.ms dist/sdbm.c
# Wrapped by oz at yunexus on Sat Dec 15 10:24:20 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'dist/readme.ms' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/readme.ms'\"
else
echo shar: Extracting \"'dist/readme.ms'\" \(11691 characters\)
sed "s/^X//" >'dist/readme.ms' <<'END_OF_FILE'
X.\" tbl | readme.ms | [tn]roff -ms | ...
X.\" note the "C" (courier) and "CB" fonts: you will probably have to
X.\" change these.
X.\" $Id: readme.ms,v 1.1 90/12/13 13:09:15 oz Exp Locker: oz $
X
X.de P1
X.br
X.nr dT 4
X.nf
X.ft C
X.sp .5
X.nr t \\n(dT*\\w'x'u
X.ta 1u*\\ntu 2u*\\ntu 3u*\\ntu 4u*\\ntu 5u*\\ntu 6u*\\ntu 7u*\\ntu 8u*\\ntu 9u*\\ntu 10u*\\ntu 11u*\\ntu 12u*\\ntu 13u*\\ntu 14u*\\ntu
X..
X.de P2
X.br
X.ft 1
X.br
X.sp .5
X.br
X.fi
X..
X.\" CW uses the typewriter/courier font.
X.de CW
X\fC\\$1\\fP\\$2
X..
X
X.\" Footnote numbering [by Henry Spencer]
X.\" <text>\*f for a footnote number..
X.\" .FS
X.\" \*F <footnote text>
X.\" .FE
X.\"
X.ds f \\u\\s-2\\n+f\\s+2\\d
X.nr f 0 1
X.ds F \\n+F.
X.nr F 0 1
X
X.ND
X.LP
X.TL
X\fIsdbm\fP \(em Substitute DBM
X.br
Xor
X.br
XBerkeley \fIndbm\fP for Every UN*X\** Made Simple
X.AU
XOzan (oz) Yigit
X.AI
XThe Guild of PD Software Toolmakers
XToronto - Canada
X.sp
Xoz at nexus.yorku.ca
X.LP
X.FS
XUN*X is not a trademark of any (dis)organization.
X.FE
X.sp 2
X\fIImplementation is the sincerest form of flattery. \(em L. Peter Deutsch\fP
X.SH
XA The Clone of the \fIndbm\fP library
X.PP
XThe sources accompanying this notice \(em \fIsdbm\fP \(em constitute
Xthe first public release (Dec. 1990) of a complete clone of
Xthe Berkeley UN*X \fIndbm\fP library. The \fIsdbm\fP library is meant to
Xclone the proven functionality of \fIndbm\fP as closely as possible,
Xincluding a few improvements. It is practical, easy to understand, and
Xcompatible.
XThe \fIsdbm\fP library is not derived from any licensed, proprietary or
Xcopyrighted software.
X.PP
XThe \fIsdbm\fP implementation is based on a 1978 algorithm
X[Lar78] by P.-A. (Paul) Larson known as ``Dynamic Hashing''.
XIn the course of searching for a substitute for \fIndbm\fP, I
Xprototyped three different external-hashing algorithms [Lar78, Fag79, Lit80]
Xand ultimately chose Larson's algorithm as a basis of the \fIsdbm\fP
Ximplementation. The Bell Labs
X\fIdbm\fP (and therefore \fIndbm\fP) is based on an algorithm invented by
XKen Thompson, [Tho90, Tor87] and predates Larson's work.
X.PP
XThe \fIsdbm\fR programming interface is totally compatible
Xwith \fIndbm\fP and includes a slight improvement in database initialization.
XIt is also expected to be binary-compatible under most UN*X versions that
Xsupport the \fIndbm\fP library.
X.PP
XThe \fIsdbm\fP implementation shares the shortcomings of the \fIndbm\fP
Xlibrary, as a side effect of various simplifications to the original Larson
Xalgorithm. It does produce \fIholes\fP in the page file as it writes
Xpages past the end of file. (Larson's paper include a clever solution to
Xthis problem that is a result of using the hash value directly as a block
Xaddress.) On the other hand, extensive tests seem to indicate that \fIsdbm\fP
Xcreates fewer holes in general, and the resulting pagefiles are
Xsmaller. The \fIsdbm\fP implementation is also faster than \fIndbm\fP
Xin database creation.
XUnlike the \fIndbm\fP, the \fIsdbm\fP
X.CW store
Xoperation will not ``wander away'' trying to split its
Xdata pages to insert a datum that \fIcannot\fP (due to elaborate worst-case
Xsituations) be inserted. (It will fail after a pre-defined number of attempts.)
X.SH
XImportant Compatibility Warning
X.PP
XThe \fIsdbm\fP and \fIndbm\fP
Xlibraries \fIcannot\fP share databases: one cannot read the (dir/pag)
Xdatabase created by the other. This is due to the differences
Xbetween the \fIndbm\fP and \fIsdbm\fP algorithms\**,
X.FS
XTorek's discussion [Tor87]
Xindicates that \fIdbm/ndbm\fP implementations use the hash
Xvalue to traverse the radix trie differently than \fIsdbm\fP
Xand as a result, the page indexes are generated in \fIdifferent\fP order.
XFor more information, send e-mail to the author.
X.FE
Xand the hash functions
Xused.
XIt is easy to convert between the \fIdbm/ndbm\fP databases and \fIsdbm\fP
Xby ignoring the index completely: see
X.CW dbd ,
X.CW dbu
Xetc.
X.R
X.LP
X.SH
XNotice of Intellectual Property
X.LP
X\fIThe entire\fP sdbm \fIlibrary package, as authored by me,\fP Ozan S. Yigit,
X\fIis hereby placed in the public domain.\fP As such, the author is not
Xresponsible for the consequences of use of this software, no matter how
Xawful, even if they arise from defects in it. There is no expressed or
Ximplied warranty for the \fIsdbm\fP library.
X.PP
XSince the \fIsdbm\fP
Xlibrary package is in the public domain, this \fIoriginal\fP
Xrelease or any additional public-domain releases of the modified original
Xcannot possibly (by definition) be withheld from you. Also by definition,
XYou (singular) have all the rights to this code (including the right to
Xsell without permission, the right to hoard\**
X.FS
XYou cannot really hoard something that is available to the public at
Xlarge, but try if it makes you feel any better.
X.FE
Xand the right to do other icky things as
Xyou see fit) but those rights are also granted to everyone else.
X.PP
XPlease note that all previous distributions of this software contained
Xa copyright (which is now dropped) to protect its
Xorigins and its current public domain status against any possible claims
Xand/or challenges.
X.SH
XAcknowledgments
X.PP
XMany people have been very helpful and supportive. A partial list would
Xnecessarily include Rayan Zacherissen (who contributed the man page,
Xand also hacked a MMAP version of \fIsdbm\fP),
XArnold Robbins, Chris Lewis,
XBill Davidsen, Henry Spencer, Geoff Collyer, Rich Salz (who got me started
Xin the first place), Johannes Ruschein
X(who did the minix port) and David Tilbrook. I thank you all.
X.SH
XDistribution Manifest and Notes
X.LP
XThis distribution of \fIsdbm\fP includes (at least) the following:
X.P1
X CHANGES change log
X README this file.
X biblio a small bibliography on external hashing
X dba.c a crude (n/s)dbm page file analyzer
X dbd.c a crude (n/s)dbm page file dumper (for conversion)
X dbe.1 man page for dbe.c
X dbe.c Janick's database editor
X dbm.c a dbm library emulation wrapper for ndbm/sdbm
X dbm.h header file for the above
X dbu.c a crude db management utility
X hash.c hashing function
X makefile guess.
X pair.c page-level routines (posted earlier)
X pair.h header file for the above
X readme.ms troff source for the README file
X sdbm.3 man page
X sdbm.c the real thing
X sdbm.h header file for the above
X tune.h place for tuning & portability thingies
X util.c miscellaneous
X.P2
X.PP
X.CW dbu
Xis a simple database manipulation program\** that tries to look
X.FS
XThe
X.CW dbd ,
X.CW dba ,
X.CW dbu
Xutilities are quick hacks and are not fit for production use. They were
Xdeveloped late one night, just to test out \fIsdbm\fP, and convert some
Xdatabases.
X.FE
Xlike Bell Labs'
X.CW cbt
Xutility. It is currently incomplete in functionality.
XI use
X.CW dbu
Xto test out the routines: it takes (from stdin) tab separated
Xkey/value pairs for commands like
X.CW build
Xor
X.CW insert
Xor takes keys for
Xcommands like
X.CW delete
Xor
X.CW look .
X.P1
X dbu <build|creat|look|insert|cat|delete> dbmfile
X.P2
X.PP
X.CW dba
Xis a crude analyzer of \fIdbm/sdbm/ndbm\fP
Xpage files. It scans the entire
Xpage file, reporting page level statistics, and totals at the end.
X.PP
X.CW dbd
Xis a crude dump program for \fIdbm/ndbm/sdbm\fP
Xdatabases. It ignores the
Xbitmap, and dumps the data pages in sequence. It can be used to create
Xinput for the
X.CW dbu
Xutility.
XNote that
X.CW dbd
Xwill skip any NULLs in the key and data
Xfields, thus is unsuitable to convert some peculiar databases that
Xinsist in including the terminating null.
X.PP
XI have also included a copy of the
X.CW dbe
X(\fIndbm\fP DataBase Editor) by Janick Bergeron [janick at bnr.ca] for
Xyour pleasure. You may find it more useful than the little
X.CW dbu
Xutility.
X.PP
X.CW dbm.[ch]
Xis a \fIdbm\fP library emulation on top of \fIndbm\fP
X(and hence suitable for \fIsdbm\fP). Written by Robert Elz.
X.PP
XThe \fIsdbm\fP
Xlibrary has been around in beta test for quite a long time, and from whatever
Xlittle feedback I received (maybe no news is good news), I believe it has been
Xfunctioning without any significant problems. I would, of course, appreciate
Xall fixes and/or improvements. Portability enhancements would especially be
Xuseful.
X.SH
XImplementation Issues
X.PP
XHash functions:
XThe algorithm behind \fIsdbm\fP implementation needs a good bit-scrambling
Xhash function to be effective. I ran into a set of constants for a simple
Xhash function that seem to help \fIsdbm\fP perform better than \fIndbm\fP
Xfor various inputs:
X.P1
X /*
X * polynomial conversion ignoring overflows
X * 65599 nice. 65587 even better.
X */
X long
X dbm_hash(char *str, int len) {
X register unsigned long n = 0;
X
X while (len--)
X n = n * 65599 + *str++;
X return n;
X }
X.P2
X.PP
XThere may be better hash functions for the purposes of dynamic hashing.
XTry your favorite, and check the pagefile. If it contains too many pages
Xwith too many holes, (in relation to this one for example) or if
X\fIsdbm\fP
Xsimply stops working (fails after
X.CW SPLTMAX
Xattempts to split) when you feed your
XNEWS
X.CW history
Xfile to it, you probably do not have a good hashing function.
XIf you do better (for different types of input), I would like to know
Xabout the function you use.
X.PP
XBlock sizes: It seems (from various tests on a few machines) that a page
Xfile block size
X.CW PBLKSIZ
Xof 1024 is by far the best for performance, but
Xthis also happens to limit the size of a key/value pair. Depending on your
Xneeds, you may wish to increase the page size, and also adjust
X.CW PAIRMAX
X(the maximum size of a key/value pair allowed: should always be at least
Xthree words smaller than
X.CW PBLKSIZ .)
Xaccordingly. The system-wide version of the library
Xshould probably be
Xconfigured with 1024 (distribution default), as this appears to be sufficient
Xfor most common uses of \fIsdbm\fP.
X.SH
XPortability
X.PP
XThis package has been tested in many different UN*Xes even including minix,
Xand appears to be reasonably portable. This does not mean it will port
Xeasily to non-UN*X systems.
X.SH
XNotes and Miscellaneous
X.PP
XThe \fIsdbm\fP is not a very complicated package, at least not after you
Xfamiliarize yourself with the literature on external hashing. There are
Xother interesting algorithms in existence that ensure (approximately)
Xsingle-read access to a data value associated with any key. These are
Xdirectory-less schemes such as \fIlinear hashing\fP [Lit80] (+ Larson
Xvariations), \fIspiral storage\fP [Mar79] or directory schemes such as
X\fIextensible hashing\fP [Fag79] by Fagin et al. I do hope these sources
Xprovide a reasonable playground for experimentation with other algorithms.
XSee the June 1988 issue of ACM Computing Surveys [Enb88] for an
Xexcellent overview of the field.
X.PG
X.SH
XReferences
X.LP
X.IP [Lar78] 4m
XP.-A. Larson,
X``Dynamic Hashing'', \fIBIT\fP, vol. 18, pp. 184-201, 1978.
X.IP [Tho90] 4m
XKen Thompson, \fIprivate communication\fP, Nov. 1990
X.IP [Lit80] 4m
XW. Litwin,
X`` Linear Hashing: A new tool for file and table addressing'',
X\fIProceedings of the 6th Conference on Very Large Dabatases (Montreal)\fP,
Xpp. 212-223, Very Large Database Foundation, Saratoga, Calif., 1980.
X.IP [Fag79] 4m
XR. Fagin, J. Nievergelt, N. Pippinger, and H. R. Strong,
X``Extendible Hashing - A Fast Access Method for Dynamic Files'',
X\fIACM Trans. Database Syst.\fP, vol. 4, no.3, pp. 315-344, Sept. 1979.
X.IP [Wal84] 4m
XRich Wales,
X``Discussion of "dbm" data base system'', \fIUSENET newsgroup unix.wizards\fP,
XJan. 1984.
X.IP [Tor87] 4m
XChris Torek,
X``Re: dbm.a and ndbm.a archives'', \fIUSENET newsgroup comp.unix\fP,
X1987.
X.IP [Mar79] 4m
XG. N. Martin,
X``Spiral Storage: Incrementally Augmentable Hash Addressed Storage'',
X\fITechnical Report #27\fP, University of Varwick, Coventry, U.K., 1979.
X.IP [Enb88] 4m
XR. J. Enbody and H. C. Du,
X``Dynamic Hashing Schemes'',\fIACM Computing Surveys\fP,
Xvol. 20, no. 2, pp. 85-113, June 1988.
END_OF_FILE
if test 11691 -ne `wc -c <'dist/readme.ms'`; then
echo shar: \"'dist/readme.ms'\" unpacked with wrong size!
fi
# end of 'dist/readme.ms'
fi
if test -f 'dist/sdbm.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/sdbm.c'\"
else
echo shar: Extracting \"'dist/sdbm.c'\" \(11006 characters\)
sed "s/^X//" >'dist/sdbm.c' <<'END_OF_FILE'
X/*
X * sdbm - ndbm work-alike hashed database library
X * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
X * author: oz at nexus.yorku.ca
X * status: public domain.
X *
X * core routines
X */
X
X#ifndef lint
Xstatic char rcsid[] = "$Id: sdbm.c,v 1.16 90/12/13 13:01:31 oz Exp $";
X#endif
X
X#include "sdbm.h"
X#include "tune.h"
X#include "pair.h"
X
X#include <sys/types.h>
X#include <sys/stat.h>
X#ifdef BSD42
X#include <sys/file.h>
X#else
X#include <fcntl.h>
X#include <memory.h>
X#endif
X#include <errno.h>
X#include <string.h>
X
X#ifdef __STDC__
X#include <stddef.h>
X#endif
X
X#ifndef NULL
X#define NULL 0
X#endif
X
X/*
X * externals
X */
X#ifndef sun
Xextern int errno;
X#endif
X
Xextern char *malloc proto((unsigned int));
Xextern void free proto((void *));
Xextern long lseek();
X
X/*
X * forward
X */
Xstatic int getdbit proto((DBM *, long));
Xstatic int setdbit proto((DBM *, long));
Xstatic int getpage proto((DBM *, long));
Xstatic datum getnext proto((DBM *));
Xstatic int makroom proto((DBM *, long, int));
X
X/*
X * useful macros
X */
X#define bad(x) ((x).dptr == NULL || (x).dsize <= 0)
X#define exhash(item) dbm_hash((item).dptr, (item).dsize)
X#define ioerr(db) ((db)->flags |= DBM_IOERR)
X
X#define OFF_PAG(off) (long) (off) * PBLKSIZ
X#define OFF_DIR(off) (long) (off) * DBLKSIZ
X
Xstatic long masks[] = {
X 000000000000, 000000000001, 000000000003, 000000000007,
X 000000000017, 000000000037, 000000000077, 000000000177,
X 000000000377, 000000000777, 000000001777, 000000003777,
X 000000007777, 000000017777, 000000037777, 000000077777,
X 000000177777, 000000377777, 000000777777, 000001777777,
X 000003777777, 000007777777, 000017777777, 000037777777,
X 000077777777, 000177777777, 000377777777, 000777777777,
X 001777777777, 003777777777, 007777777777, 017777777777
X};
X
Xdatum nullitem = {NULL, 0};
X
XDBM *
Xdbm_open(file, flags, mode)
Xregister char *file;
Xregister int flags;
Xregister int mode;
X{
X register DBM *db;
X register char *dirname;
X register char *pagname;
X register int n;
X
X if (file == NULL || !*file)
X return errno = EINVAL, (DBM *) NULL;
X/*
X * need space for two seperate filenames
X */
X n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2;
X
X if ((dirname = malloc((unsigned) n)) == NULL)
X return errno = ENOMEM, (DBM *) NULL;
X/*
X * build the file names
X */
X dirname = strcat(strcpy(dirname, file), DIRFEXT);
X pagname = strcpy(dirname + strlen(dirname) + 1, file);
X pagname = strcat(pagname, PAGFEXT);
X
X db = dbm_prep(dirname, pagname, flags, mode);
X free((char *) dirname);
X return db;
X}
X
XDBM *
Xdbm_prep(dirname, pagname, flags, mode)
Xchar *dirname;
Xchar *pagname;
Xint flags;
Xint mode;
X{
X register DBM *db;
X struct stat dstat;
X
X if ((db = (DBM *) malloc(sizeof(DBM))) == NULL)
X return errno = ENOMEM, (DBM *) NULL;
X
X db->flags = 0;
X db->hmask = 0;
X db->blkptr = 0;
X db->keyptr = 0;
X/*
X * adjust user flags so that WRONLY becomes RDWR,
X * as required by this package. Also set our internal
X * flag for RDONLY.
X */
X if (flags & O_WRONLY)
X flags = (flags & ~O_WRONLY) | O_RDWR;
X if (flags & O_RDONLY)
X db->flags = DBM_RDONLY;
X/*
X * open the files in sequence, and stat the dirfile.
X * If we fail anywhere, undo everything, return NULL.
X */
X if ((db->pagf = open(pagname, flags, mode)) > -1) {
X if ((db->dirf = open(dirname, flags, mode)) > -1) {
X/*
X * need the dirfile size to establish max bit number.
X */
X if (fstat(db->dirf, &dstat) == 0) {
X/*
X * zero size: either a fresh database, or one with a single,
X * unsplit data page: dirpage is all zeros.
X */
X db->dirbno = (!dstat.st_size) ? 0 : -1;
X db->pagbno = -1;
X db->maxbno = dstat.st_size * BYTESIZ;
X
X (void) memset(db->pagbuf, 0, PBLKSIZ);
X (void) memset(db->dirbuf, 0, DBLKSIZ);
X /*
X * success
X */
X return db;
X }
X (void) close(db->dirf);
X }
X (void) close(db->pagf);
X }
X free((char *) db);
X return (DBM *) NULL;
X}
X
Xvoid
Xdbm_close(db)
Xregister DBM *db;
X{
X if (db == NULL)
X errno = EINVAL;
X else {
X (void) close(db->dirf);
X (void) close(db->pagf);
X free((char *) db);
X }
X}
X
Xdatum
Xdbm_fetch(db, key)
Xregister DBM *db;
Xdatum key;
X{
X if (db == NULL || bad(key))
X return errno = EINVAL, nullitem;
X
X if (getpage(db, exhash(key)))
X return getpair(db->pagbuf, key);
X
X return ioerr(db), nullitem;
X}
X
Xint
Xdbm_delete(db, key)
Xregister DBM *db;
Xdatum key;
X{
X if (db == NULL || bad(key))
X return errno = EINVAL, -1;
X if (dbm_rdonly(db))
X return errno = EPERM, -1;
X
X if (getpage(db, exhash(key))) {
X if (!delpair(db->pagbuf, key))
X return -1;
X/*
X * update the page file
X */
X if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
X || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
X return ioerr(db), -1;
X
X return 0;
X }
X
X return ioerr(db), -1;
X}
X
Xint
Xdbm_store(db, key, val, flags)
Xregister DBM *db;
Xdatum key;
Xdatum val;
Xint flags;
X{
X int need;
X register long hash;
X
X if (db == NULL || bad(key))
X return errno = EINVAL, -1;
X if (dbm_rdonly(db))
X return errno = EPERM, -1;
X
X need = key.dsize + val.dsize;
X/*
X * is the pair too big (or too small) for this database ??
X */
X if (need < 0 || need > PAIRMAX)
X return errno = EINVAL, -1;
X
X if (getpage(db, (hash = exhash(key)))) {
X/*
X * if we need to replace, delete the key/data pair
X * first. If it is not there, ignore.
X */
X if (flags == DBM_REPLACE)
X (void) delpair(db->pagbuf, key);
X#ifdef SEEDUPS
X else if (duppair(db->pagbuf, key))
X return 1;
X#endif
X/*
X * if we do not have enough room, we have to split.
X */
X if (!fitpair(db->pagbuf, need))
X if (!makroom(db, hash, need))
X return ioerr(db), -1;
X/*
X * we have enough room or split is successful. insert the key,
X * and update the page file.
X */
X (void) putpair(db->pagbuf, key, val);
X
X if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
X || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
X return ioerr(db), -1;
X /*
X * success
X */
X return 0;
X }
X
X return ioerr(db), -1;
X}
X
X/*
X * makroom - make room by splitting the overfull page
X * this routine will attempt to make room for SPLTMAX times before
X * giving up.
X */
Xstatic int
Xmakroom(db, hash, need)
Xregister DBM *db;
Xlong hash;
Xint need;
X{
X long newp;
X char twin[PBLKSIZ];
X char *pag = db->pagbuf;
X char *new = twin;
X register int smax = SPLTMAX;
X
X do {
X/*
X * split the current page
X */
X (void) splpage(pag, new, db->hmask + 1);
X/*
X * address of the new page
X */
X newp = (hash & db->hmask) | (db->hmask + 1);
X
X/*
X * write delay, read avoidence/cache shuffle:
X * select the page for incoming pair: if key is to go to the new page,
X * write out the previous one, and copy the new one over, thus making
X * it the current page. If not, simply write the new page, and we are
X * still looking at the page of interest. current page is not updated
X * here, as dbm_store will do so, after it inserts the incoming pair.
X */
X if (hash & (db->hmask + 1)) {
X if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
X || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
X return 0;
X db->pagbno = newp;
X (void) memcpy(pag, new, PBLKSIZ);
X }
X else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0
X || write(db->pagf, new, PBLKSIZ) < 0)
X return 0;
X
X if (!setdbit(db, db->curbit))
X return 0;
X/*
X * see if we have enough room now
X */
X if (fitpair(pag, need))
X return 1;
X/*
X * try again... update curbit and hmask as getpage would have
X * done. because of our update of the current page, we do not
X * need to read in anything. BUT we have to write the current
X * [deferred] page out, as the window of failure is too great.
X */
X db->curbit = 2 * db->curbit +
X (hash & (db->hmask + 1)) ? 2 : 1;
X db->hmask |= (db->hmask + 1);
X
X if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
X || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
X return 0;
X
X } while (--smax);
X/*
X * if we are here, this is real bad news. After SPLTMAX splits,
X * we still cannot fit the key. say goodnight.
X */
X#ifdef BADMESS
X (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
X#endif
X return 0;
X
X}
X
X/*
X * the following two routines will break if
X * deletions aren't taken into account. (ndbm bug)
X */
Xdatum
Xdbm_firstkey(db)
Xregister DBM *db;
X{
X if (db == NULL)
X return errno = EINVAL, nullitem;
X/*
X * start at page 0
X */
X if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0
X || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
X return ioerr(db), nullitem;
X db->pagbno = 0;
X db->blkptr = 0;
X db->keyptr = 0;
X
X return getnext(db);
X}
X
Xdatum
Xdbm_nextkey(db)
Xregister DBM *db;
X{
X if (db == NULL)
X return errno = EINVAL, nullitem;
X return getnext(db);
X}
X
X/*
X * all important binary trie traversal
X */
Xstatic int
Xgetpage(db, hash)
Xregister DBM *db;
Xregister long hash;
X{
X register int hbit;
X register long dbit;
X register long pagb;
X
X dbit = 0;
X hbit = 0;
X while (dbit < db->maxbno && getdbit(db, dbit))
X dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
X
X debug(("dbit: %d...", dbit));
X
X db->curbit = dbit;
X db->hmask = masks[hbit];
X
X pagb = hash & db->hmask;
X/*
X * see if the block we need is already in memory.
X * note: this lookaside cache has about 10% hit rate.
X */
X if (pagb != db->pagbno) {
X/*
X * note: here, we assume a "hole" is read as 0s.
X * if not, must zero pagbuf first.
X */
X if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0
X || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
X return 0;
X if (!chkpage(db->pagbuf))
X return 0;
X db->pagbno = pagb;
X
X debug(("pag read: %d\n", pagb));
X }
X return 1;
X}
X
Xstatic int
Xgetdbit(db, dbit)
Xregister DBM *db;
Xregister long dbit;
X{
X register long c;
X register long dirb;
X
X c = dbit / BYTESIZ;
X dirb = c / DBLKSIZ;
X
X if (dirb != db->dirbno) {
X if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
X || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
X return 0;
X db->dirbno = dirb;
X
X debug(("dir read: %d\n", dirb));
X }
X
X return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
X}
X
Xstatic int
Xsetdbit(db, dbit)
Xregister DBM *db;
Xregister long dbit;
X{
X register long c;
X register long dirb;
X
X c = dbit / BYTESIZ;
X dirb = c / DBLKSIZ;
X
X if (dirb != db->dirbno) {
X if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
X || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
X return 0;
X db->dirbno = dirb;
X
X debug(("dir read: %d\n", dirb));
X }
X
X db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
X
X if (dbit >= db->maxbno)
X db->maxbno += DBLKSIZ * BYTESIZ;
X
X if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
X || write(db->dirf, db->dirbuf, DBLKSIZ) < 0)
X return 0;
X
X return 1;
X}
X
X/*
X * getnext - get the next key in the page, and if done with
X * the page, try the next page in sequence
X */
Xstatic datum
Xgetnext(db)
Xregister DBM *db;
X{
X datum key;
X
X for (;;) {
X db->keyptr++;
X key = getnkey(db->pagbuf, db->keyptr);
X if (key.dptr != NULL)
X return key;
X/*
X * we either run out, or there is nothing on this page..
X * try the next one... If we lost our position on the
X * file, we will have to seek.
X */
X db->keyptr = 0;
X if (db->pagbno != db->blkptr++)
X if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0)
X break;
X db->pagbno = db->blkptr;
X if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0)
X break;
X if (!chkpage(db->pagbuf))
X break;
X }
X
X return ioerr(db), nullitem;
X}
END_OF_FILE
if test 11006 -ne `wc -c <'dist/sdbm.c'`; then
echo shar: \"'dist/sdbm.c'\" unpacked with wrong size!
fi
# end of 'dist/sdbm.c'
fi
echo shar: End of archive 2 \(of 2\).
cp /dev/null ark2isdone
MISSING=""
for I in 1 2 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked both archives.
rm -f ark[1-9]isdone
else
echo You still need to unpack the following archives:
echo " " ${MISSING}
fi
## End of shell archive.
exit 0
More information about the Alt.sources
mailing list