Source Code 1992 March

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

/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 2 / 2386 < prev next >

Wrap

Internet Message Format | 1990-12-28 | 24.8 KB

From: oz@nexus.YorkU.CA (Ozan Yigit) Newsgroups: alt.sources Subject: sdbm part 2 Message-ID: <19120@yunexus.YorkU.CA> Date: 15 Dec 90 15:38:34 GMT #! /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@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@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@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@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