.\" tbl | readme.ms | [tn]roff -ms | ....\" note the "C" (courier) and "CB" fonts: you will probably have to.\" change these..\" $Id: readme.ms,v 1.1 90/12/13 13:09:15 oz Exp Locker: oz $.de P1.br.nr dT 4.nf.ft C.sp .5.nr t \\n(dT*\\w'x'u.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...de P2.br.ft 1.br.sp .5.br.fi...\" CW uses the typewriter/courier font..de CW\fC\\$1\\fP\\$2...\" Footnote numbering [by Henry Spencer].\" <text>\*f for a footnote number...\" .FS.\" \*F <footnote text>.\" .FE.\".ds f \\u\\s-2\\n+f\\s+2\\d.nr f 0 1.ds F \\n+F..nr F 0 1.ND.LP.TL\fIsdbm\fP \(em Substitute DBM.bror.brBerkeley \fIndbm\fP for Every UN*X\** Made Simple.AUOzan (oz) Yigit.AIThe Guild of PD Software ToolmakersToronto - Canada.spoz@nexus.yorku.ca.LP.FSUN*X is not a trademark of any (dis)organization..FE.sp 2\fIImplementation is the sincerest form of flattery. \(em L. Peter Deutsch\fP.SHA The Clone of the \fIndbm\fP library.PPThe sources accompanying this notice \(em \fIsdbm\fP \(em constitutethe first public release (Dec. 1990) of a complete clone ofthe Berkeley UN*X \fIndbm\fP library. The \fIsdbm\fP library is meant toclone the proven functionality of \fIndbm\fP as closely as possible,including a few improvements. It is practical, easy to understand, andcompatible.The \fIsdbm\fP library is not derived from any licensed, proprietary orcopyrighted software..PPThe \fIsdbm\fP implementation is based on a 1978 algorithm[Lar78] by P.-A. (Paul) Larson known as ``Dynamic Hashing''.In the course of searching for a substitute for \fIndbm\fP, Iprototyped three different external-hashing algorithms [Lar78, Fag79, Lit80]and ultimately chose Larson's algorithm as a basis of the \fIsdbm\fPimplementation. The Bell Labs\fIdbm\fP (and therefore \fIndbm\fP) is based on an algorithm invented byKen Thompson, [Tho90, Tor87] and predates Larson's work..PPThe \fIsdbm\fR programming interface is totally compatiblewith \fIndbm\fP and includes a slight improvement in database initialization.It is also expected to be binary-compatible under most UN*X versions thatsupport the \fIndbm\fP library..PPThe \fIsdbm\fP implementation shares the shortcomings of the \fIndbm\fPlibrary, as a side effect of various simplifications to the original Larsonalgorithm. It does produce \fIholes\fP in the page file as it writespages past the end of file. (Larson's paper include a clever solution tothis problem that is a result of using the hash value directly as a blockaddress.) On the other hand, extensive tests seem to indicate that \fIsdbm\fPcreates fewer holes in general, and the resulting pagefiles aresmaller. The \fIsdbm\fP implementation is also faster than \fIndbm\fPin database creation.Unlike the \fIndbm\fP, the \fIsdbm\fP.CW storeoperation will not ``wander away'' trying to split itsdata pages to insert a datum that \fIcannot\fP (due to elaborate worst-casesituations) be inserted. (It will fail after a pre-defined number of attempts.).SHImportant Compatibility Warning.PPThe \fIsdbm\fP and \fIndbm\fPlibraries \fIcannot\fP share databases: one cannot read the (dir/pag)database created by the other. This is due to the differencesbetween the \fIndbm\fP and \fIsdbm\fP algorithms\**, .FSTorek's discussion [Tor87]indicates that \fIdbm/ndbm\fP implementations use the hashvalue to traverse the radix trie differently than \fIsdbm\fPand as a result, the page indexes are generated in \fIdifferent\fP order.For more information, send e-mail to the author..FEand the hash functionsused.It is easy to convert between the \fIdbm/ndbm\fP databases and \fIsdbm\fPby ignoring the index completely: see.CW dbd ,.CW dbuetc..R.LP.SHNotice of Intellectual Property.LP\fIThe entire\fP sdbm  \fIlibrary package, as authored by me,\fP Ozan S. Yigit,\fIis hereby placed in the public domain.\fP As such, the author is notresponsible for the consequences of use of this software, no matter howawful, even if they arise from defects in it. There is no expressed orimplied warranty for the \fIsdbm\fP library..PPSince the \fIsdbm\fPlibrary package is in the public domain, this \fIoriginal\fPrelease or any additional public-domain releases of the modified originalcannot possibly (by definition) be withheld from you. Also by definition,You (singular) have all the rights to this code (including the right tosell without permission, the right to hoard\**.FSYou cannot really hoard something that is available to the public atlarge, but try if it makes you feel any better..FEand the right to do other icky things asyou see fit) but those rights are also granted to everyone else..PPPlease note that all previous distributions of this software containeda copyright (which is now dropped) to protect itsorigins and its current public domain status against any possible claimsand/or challenges..SHAcknowledgments.PPMany people have been very helpful and supportive.  A partial list wouldnecessarily include Rayan Zacherissen (who contributed the man page,and also hacked a MMAP version of \fIsdbm\fP),Arnold Robbins, Chris Lewis,Bill Davidsen, Henry Spencer, Geoff Collyer, Rich Salz (who got me startedin the first place), Johannes Ruschein(who did the minix port) and David Tilbrook. I thank you all..SHDistribution Manifest and Notes.LPThis distribution of \fIsdbm\fP includes (at least) the following:.P1	CHANGES		change log	README		this file.	biblio		a small bibliography on external hashing	dba.c		a crude (n/s)dbm page file analyzer	dbd.c		a crude (n/s)dbm page file dumper (for conversion)	dbe.1		man page for dbe.c	dbe.c		Janick's database editor	dbm.c		a dbm library emulation wrapper for ndbm/sdbm	dbm.h		header file for the above	dbu.c		a crude db management utility	hash.c		hashing function	makefile	guess.	pair.c		page-level routines (posted earlier)	pair.h		header file for the above	readme.ms	troff source for the README file	sdbm.3		man page	sdbm.c		the real thing	sdbm.h		header file for the above	tune.h		place for tuning & portability thingies	util.c		miscellaneous.P2.PP.CW dbuis a simple database manipulation program\** that tries to look.FSThe .CW dbd ,.CW dba ,.CW dbuutilities are quick hacks and are not fit for production use. They weredeveloped late one night, just to test out \fIsdbm\fP, and convert somedatabases..FElike Bell Labs'.CW cbtutility. It is currently incomplete in functionality.I use.CW dbuto test out the routines: it takes (from stdin) tab separatedkey/value pairs for commands like.CW buildor.CW insertor takes keys forcommands like.CW deleteor.CW look ..P1	dbu <build|creat|look|insert|cat|delete> dbmfile.P2.PP.CW dbais a crude analyzer of \fIdbm/sdbm/ndbm\fPpage files. It scans the entirepage file, reporting page level statistics, and totals at the end..PP.CW dbdis a crude dump program for \fIdbm/ndbm/sdbm\fPdatabases. It ignores thebitmap, and dumps the data pages in sequence. It can be used to createinput for the.CW dbu utility.Note that.CW dbdwill skip any NULLs in the key and datafields, thus is unsuitable to convert some peculiar databases thatinsist in including the terminating null..PPI have also included a copy of the.CW dbe(\fIndbm\fP DataBase Editor) by Janick Bergeron [janick@bnr.ca] foryour pleasure. You may find it more useful than the little.CW dbuutility..PP.CW dbm.[ch]is a \fIdbm\fP library emulation on top of \fIndbm\fP(and hence suitable for \fIsdbm\fP). Written by Robert Elz..PPThe \fIsdbm\fPlibrary has been around in beta test for quite a long time, and from whateverlittle feedback I received (maybe no news is good news), I believe it has beenfunctioning without any significant problems. I would, of course, appreciateall fixes and/or improvements. Portability enhancements would especially beuseful..SHImplementation Issues.PPHash functions:The algorithm behind \fIsdbm\fP implementation needs a good bit-scramblinghash function to be effective. I ran into a set of constants for a simplehash function that seem to help \fIsdbm\fP perform better than \fIndbm\fPfor various inputs:.P1	/*	 * polynomial conversion ignoring overflows	 * 65599 nice. 65587 even better.	 */	long	dbm_hash(char *str, int len) {		register unsigned long n = 0;			while (len--)			n = n * 65599 + *str++;		return n;	}.P2.PPThere may be better hash functions for the purposes of dynamic hashing.Try your favorite, and check the pagefile. If it contains too many pageswith too many holes, (in relation to this one for example) or if\fIsdbm\fPsimply stops working (fails after .CW SPLTMAXattempts to split) when you feed yourNEWS .CW historyfile to it, you probably do not have a good hashing function.If you do better (for different types of input), I would like to knowabout the function you use..PPBlock sizes: It seems (from various tests on a few machines) that a pagefile block size.CW PBLKSIZof 1024 is by far the best for performance, butthis also happens to limit the size of a key/value pair. Depending on yourneeds, you may wish to increase the page size, and also adjust.CW PAIRMAX(the maximum size of a key/value pair allowed: should always be at leastthree words smaller than.CW PBLKSIZ .)accordingly. The system-wide version of the libraryshould probably beconfigured with 1024 (distribution default), as this appears to be sufficientfor most common uses of \fIsdbm\fP..SHPortability.PPThis package has been tested in many different UN*Xes even including minix,and appears to be reasonably portable. This does not mean it will porteasily to non-UN*X systems..SHNotes and Miscellaneous.PPThe \fIsdbm\fP is not a very complicated package, at least not after youfamiliarize yourself with the literature on external hashing. There areother interesting algorithms in existence that ensure (approximately)single-read access to a data value associated with any key. These aredirectory-less schemes such as \fIlinear hashing\fP [Lit80] (+ Larsonvariations), \fIspiral storage\fP [Mar79] or directory schemes such as\fIextensible hashing\fP [Fag79] by Fagin et al. I do hope these sourcesprovide a reasonable playground for experimentation with other algorithms.See the June 1988 issue of ACM Computing Surveys [Enb88] for anexcellent overview of the field. .PG.SHReferences.LP.IP [Lar78] 4mP.-A. Larson,``Dynamic Hashing'', \fIBIT\fP, vol.  18,  pp. 184-201, 1978..IP [Tho90] 4mKen Thompson, \fIprivate communication\fP, Nov. 1990.IP [Lit80] 4mW. Litwin,`` Linear Hashing: A new tool  for  file  and table addressing'',\fIProceedings of the 6th Conference on Very Large  Dabatases  (Montreal)\fP,pp.  212-223,  Very Large Database Foundation, Saratoga, Calif., 1980..IP [Fag79] 4mR. Fagin, J.  Nievergelt,  N.  Pippinger,  and  H.  R. Strong,``Extendible Hashing - A Fast Access Method for Dynamic Files'',\fIACM Trans. Database Syst.\fP, vol. 4,  no.3, pp. 315-344, Sept. 1979..IP [Wal84] 4mRich Wales,``Discussion of "dbm" data base system'', \fIUSENET newsgroup unix.wizards\fP,Jan. 1984..IP [Tor87] 4mChris Torek,``Re:  dbm.a  and  ndbm.a  archives'', \fIUSENET newsgroup comp.unix\fP,1987..IP [Mar79] 4mG. N. Martin,``Spiral Storage: Incrementally  Augmentable  Hash  Addressed  Storage'',\fITechnical Report #27\fP, University of Varwick, Coventry, U.K., 1979..IP [Enb88] 4mR. J. Enbody and H. C. Du,``Dynamic Hashing  Schemes'',\fIACM Computing Surveys\fP,vol. 20, no. 2, pp. 85-113, June 1988.