diff options
Diffstat (limited to 'ext/dbm/sdbm/.r')
| -rwxr-xr-x | ext/dbm/sdbm/.r | 5884 |
1 files changed, 0 insertions, 5884 deletions
diff --git a/ext/dbm/sdbm/.r b/ext/dbm/sdbm/.r deleted file mode 100755 index c72dbf15f5..0000000000 --- a/ext/dbm/sdbm/.r +++ /dev/null @@ -1,5884 +0,0 @@ -if test -f 'CHANGES' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'CHANGES'\" -else -echo shar: Extracting \"'CHANGES'\" \(900 characters\) -sed "s/^X//" >'CHANGES' <<'END_OF_FILE' -XChanges from the earlier BETA releases. -X -Xo dbm_prep does everything now, so dbm_open is just a simple -X wrapper that builds the default filenames. dbm_prep no longer -X requires a (DBM *) db parameter: it allocates one itself. It -X returns (DBM *) db or (DBM *) NULL. -X -Xo makroom is now reliable. In the common-case optimization of the page -X split, the page into which the incoming key/value pair is to be inserted -X is write-deferred (if the split is successful), thereby saving a cosly -X write. BUT, if the split does not make enough room (unsuccessful), the -X deferred page is written out, as the failure-window is now dependent on -X the number of split attempts. -X -Xo if -DDUFF is defined, hash function will also use the DUFF construct. -X This may look like a micro-performance tweak (maybe it is), but in fact, -X the hash function is the third most-heavily used function, after read -X and write. -END_OF_FILE -if test 900 -ne `wc -c <'CHANGES'`; then - echo shar: \"'CHANGES'\" unpacked with wrong size! -fi -# end of 'CHANGES' -fi -if test -f 'COMPARE' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'COMPARE'\" -else -echo shar: Extracting \"'COMPARE'\" \(2832 characters\) -sed "s/^X//" >'COMPARE' <<'END_OF_FILE' -X -XScript started on Thu Sep 28 15:41:06 1989 -X% uname -a -Xtitan titan 4_0 UMIPS mips -X% make all x-dbm -X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dbm.c -X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c sdbm.c -X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c pair.c -X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c hash.c -X ar cr libsdbm.a sdbm.o pair.o hash.o -X ranlib libsdbm.a -X cc -o dbm dbm.o libsdbm.a -X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dba.c -X cc -o dba dba.o -X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dbd.c -X cc -o dbd dbd.o -X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -o x-dbm dbm.o -X% -X% -X% wc history -X 65110 218344 3204883 history -X% -X% /bin/time dbm build foo <history -X -Xreal 5:56.9 -Xuser 13.3 -Xsys 26.3 -X% ls -s -Xtotal 14251 -X 5 README 2 dbd.c 1 hash.c 1 pair.h -X 0 SCRIPT 5 dbd.o 1 hash.o 5 pair.o -X 1 WISHLIST 62 dbm 3130 history 1 port.h -X 46 dba 5 dbm.c 11 howtodbm.txt 11 sdbm.c -X 3 dba.c 8 dbm.o 14 libsdbm.a 2 sdbm.h -X 6 dba.o 4 foo.dir 1 makefile 8 sdbm.o -X 46 dbd 10810 foo.pag 6 pair.c 60 x-dbm -X% ls -l foo.* -X-rw-r--r-- 1 oz 4096 Sep 28 15:48 foo.dir -X-rw-r--r-- 1 oz 11069440 Sep 28 15:48 foo.pag -X% -X% /bin/time x-dbm build bar <history -X -Xreal 5:59.4 -Xuser 24.7 -Xsys 29.1 -X% -X% ls -s -Xtotal 27612 -X 5 README 46 dbd 1 hash.c 5 pair.o -X 1 SCRIPT 2 dbd.c 1 hash.o 1 port.h -X 1 WISHLIST 5 dbd.o 3130 history 11 sdbm.c -X 4 bar.dir 62 dbm 11 howtodbm.txt 2 sdbm.h -X13356 bar.pag 5 dbm.c 14 libsdbm.a 8 sdbm.o -X 46 dba 8 dbm.o 1 makefile 60 x-dbm -X 3 dba.c 4 foo.dir 6 pair.c -X 6 dba.o 10810 foo.pag 1 pair.h -X% -X% ls -l bar.* -X-rw-r--r-- 1 oz 4096 Sep 28 15:54 bar.dir -X-rw-r--r-- 1 oz 13676544 Sep 28 15:54 bar.pag -X% -X% dba foo | tail -X#10801: ok. no entries. -X#10802: ok. no entries. -X#10803: ok. no entries. -X#10804: ok. no entries. -X#10805: ok. no entries. -X#10806: ok. no entries. -X#10807: ok. no entries. -X#10808: ok. no entries. -X#10809: ok. 11 entries 67% used free 337. -X10810 pages (6036 holes): 65073 entries -X% -X% dba bar | tail -X#13347: ok. no entries. -X#13348: ok. no entries. -X#13349: ok. no entries. -X#13350: ok. no entries. -X#13351: ok. no entries. -X#13352: ok. no entries. -X#13353: ok. no entries. -X#13354: ok. no entries. -X#13355: ok. 7 entries 33% used free 676. -X13356 pages (8643 holes): 65073 entries -X% -X% exit -Xscript done on Thu Sep 28 16:08:45 1989 -X -END_OF_FILE -if test 2832 -ne `wc -c <'COMPARE'`; then - echo shar: \"'COMPARE'\" unpacked with wrong size! -fi -# end of 'COMPARE' -fi -if test -f 'README' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'README'\" -else -echo shar: Extracting \"'README'\" \(11457 characters\) -sed "s/^X//" >'README' <<'END_OF_FILE' -X -X -X -X -X -X -X sdbm - Substitute DBM -X or -X Berkeley ndbm for Every UN*X[1] Made Simple -X -X Ozan (oz) Yigit -X -X The Guild of PD Software Toolmakers -X Toronto - Canada -X -X oz@nexus.yorku.ca -X -X -X -XImplementation is the sincerest form of flattery. - L. Peter -XDeutsch -X -XA The Clone of the ndbm library -X -X The sources accompanying this notice - sdbm - consti- -Xtute the first public release (Dec. 1990) of a complete -Xclone of the Berkeley UN*X ndbm library. The sdbm library is -Xmeant to clone the proven functionality of ndbm as closely -Xas possible, including a few improvements. It is practical, -Xeasy to understand, and compatible. The sdbm library is not -Xderived from any licensed, proprietary or copyrighted -Xsoftware. -X -X The sdbm 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 ndbm, I pro- -Xtotyped three different external-hashing algorithms [Lar78, -XFag79, Lit80] and ultimately chose Larson's algorithm as a -Xbasis of the sdbm implementation. The Bell Labs dbm (and -Xtherefore ndbm) is based on an algorithm invented by Ken -XThompson, [Tho90, Tor87] and predates Larson's work. -X -X The sdbm programming interface is totally compatible -Xwith ndbm and includes a slight improvement in database ini- -Xtialization. It is also expected to be binary-compatible -Xunder most UN*X versions that support the ndbm library. -X -X The sdbm implementation shares the shortcomings of the -Xndbm library, as a side effect of various simplifications to -Xthe original Larson algorithm. It does produce holes in the -Xpage file as it writes pages past the end of file. (Larson's -Xpaper include a clever solution to this problem that is a -Xresult of using the hash value directly as a block address.) -XOn the other hand, extensive tests seem to indicate that -Xsdbm creates fewer holes in general, and the resulting page- -Xfiles are smaller. The sdbm implementation is also faster -Xthan ndbm in database creation. Unlike the ndbm, the sdbm -X_________________________ -X -X [1] UN*X is not a trademark of any (dis)organization. -X -X -X -X -X -X -X -X -X -X - 2 - -X -X -Xstore operation will not ``wander away'' trying to split its -Xdata pages to insert a datum that cannot (due to elaborate -Xworst-case situations) be inserted. (It will fail after a -Xpre-defined number of attempts.) -X -XImportant Compatibility Warning -X -X The sdbm and ndbm libraries cannot share databases: one -Xcannot read the (dir/pag) database created by the other. -XThis is due to the differences between the ndbm and sdbm -Xalgorithms[2], and the hash functions used. It is easy to -Xconvert between the dbm/ndbm databases and sdbm by ignoring -Xthe index completely: see dbd, dbu etc. -X -X -XNotice of Intellectual Property -X -XThe entire sdbm library package, as authored by me, Ozan S. -XYigit, is hereby placed in the public domain. As such, the -Xauthor is not responsible for the consequences of use of -Xthis software, no matter how awful, even if they arise from -Xdefects in it. There is no expressed or implied warranty for -Xthe sdbm library. -X -X Since the sdbm library package is in the public domain, -Xthis original release or any additional public-domain -Xreleases of the modified original cannot possibly (by defin- -Xition) be withheld from you. Also by definition, You (singu- -Xlar) have all the rights to this code (including the right -Xto sell without permission, the right to hoard[3] and the -Xright to do other icky things as you see fit) but those -Xrights are also granted to everyone else. -X -X Please note that all previous distributions of this -Xsoftware contained a copyright (which is now dropped) to -Xprotect its origins and its current public domain status -Xagainst any possible claims and/or challenges. -X -XAcknowledgments -X -X Many people have been very helpful and supportive. A -Xpartial list would necessarily include Rayan Zacherissen -X(who contributed the man page, and also hacked a MMAP -X_________________________ -X -X [2] Torek's discussion [Tor87] indicates that -Xdbm/ndbm implementations use the hash value to traverse -Xthe radix trie differently than sdbm and as a result, -Xthe page indexes are generated in different order. For -Xmore information, send e-mail to the author. -X [3] You cannot really hoard something that is avail- -Xable to the public at large, but try if it makes you -Xfeel any better. -X -X -X -X -X -X -X -X -X -X -X - 3 - -X -X -Xversion of sdbm), Arnold Robbins, Chris Lewis, Bill David- -Xsen, Henry Spencer, Geoff Collyer, Rich Salz (who got me -Xstarted in the first place), Johannes Ruschein (who did the -Xminix port) and David Tilbrook. I thank you all. -X -XDistribution Manifest and Notes -X -XThis distribution of sdbm includes (at least) the following: -X -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 -X dbu is a simple database manipulation program[4] that -Xtries to look like Bell Labs' cbt utility. It is currently -Xincomplete in functionality. I use dbu to test out the rou- -Xtines: it takes (from stdin) tab separated key/value pairs -Xfor commands like build or insert or takes keys for commands -Xlike delete or look. -X -X dbu <build|creat|look|insert|cat|delete> dbmfile -X -X dba is a crude analyzer of dbm/sdbm/ndbm page files. It -Xscans the entire page file, reporting page level statistics, -Xand totals at the end. -X -X dbd is a crude dump program for dbm/ndbm/sdbm data- -Xbases. It ignores the bitmap, and dumps the data pages in -Xsequence. It can be used to create input for the dbu util- -Xity. Note that dbd will skip any NULLs in the key and data -Xfields, thus is unsuitable to convert some peculiar -X_________________________ -X -X [4] The dbd, dba, dbu utilities are quick hacks and -Xare not fit for production use. They were developed -Xlate one night, just to test out sdbm, and convert some -Xdatabases. -X -X -X -X -X -X -X -X -X -X - 4 - -X -X -Xdatabases that insist in including the terminating null. -X -X I have also included a copy of the dbe (ndbm DataBase -XEditor) by Janick Bergeron [janick@bnr.ca] for your pleas- -Xure. You may find it more useful than the little dbu util- -Xity. -X -X dbm.[ch] is a dbm library emulation on top of ndbm (and -Xhence suitable for sdbm). Written by Robert Elz. -X -X The sdbm library has been around in beta test for quite -Xa long time, and from whatever little feedback I received -X(maybe no news is good news), I believe it has been func- -Xtioning without any significant problems. I would, of -Xcourse, appreciate all fixes and/or improvements. Portabil- -Xity enhancements would especially be useful. -X -XImplementation Issues -X -X Hash functions: The algorithm behind sdbm implementa- -Xtion needs a good bit-scrambling hash function to be effec- -Xtive. I ran into a set of constants for a simple hash func- -Xtion that seem to help sdbm perform better than ndbm for -Xvarious inputs: -X -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 -X There may be better hash functions for the purposes of -Xdynamic hashing. Try your favorite, and check the pagefile. -XIf it contains too many pages with too many holes, (in rela- -Xtion to this one for example) or if sdbm simply stops work- -Xing (fails after SPLTMAX attempts to split) when you feed -Xyour NEWS history file to it, you probably do not have a -Xgood hashing function. If you do better (for different -Xtypes of input), I would like to know about the function you -Xuse. -X -X Block sizes: It seems (from various tests on a few -Xmachines) that a page file block size PBLKSIZ of 1024 is by -Xfar the best for performance, but this also happens to limit -Xthe size of a key/value pair. Depending on your needs, you -Xmay wish to increase the page size, and also adjust PAIRMAX -X(the maximum size of a key/value pair allowed: should always -X -X -X -X -X -X -X -X -X -X - 5 - -X -X -Xbe at least three words smaller than PBLKSIZ.) accordingly. -XThe system-wide version of the library should probably be -Xconfigured with 1024 (distribution default), as this appears -Xto be sufficient for most common uses of sdbm. -X -XPortability -X -X This package has been tested in many different UN*Xes -Xeven including minix, and appears to be reasonably portable. -XThis does not mean it will port easily to non-UN*X systems. -X -XNotes and Miscellaneous -X -X The sdbm is not a very complicated package, at least -Xnot after you familiarize yourself with the literature on -Xexternal hashing. There are other interesting algorithms in -Xexistence that ensure (approximately) single-read access to -Xa data value associated with any key. These are directory- -Xless schemes such as linear hashing [Lit80] (+ Larson varia- -Xtions), spiral storage [Mar79] or directory schemes such as -Xextensible hashing [Fag79] by Fagin et al. I do hope these -Xsources provide a reasonable playground for experimentation -Xwith other algorithms. See the June 1988 issue of ACM Com- -Xputing Surveys [Enb88] for an excellent overview of the -Xfield. -X -XReferences -X -X -X[Lar78] -X P.-A. Larson, ``Dynamic Hashing'', BIT, vol. 18, pp. -X 184-201, 1978. -X -X[Tho90] -X Ken Thompson, private communication, Nov. 1990 -X -X[Lit80] -X W. Litwin, `` Linear Hashing: A new tool for file and -X table addressing'', Proceedings of the 6th Conference on -X Very Large Dabatases (Montreal), pp. 212-223, Very -X Large Database Foundation, Saratoga, Calif., 1980. -X -X[Fag79] -X R. Fagin, J. Nievergelt, N. Pippinger, and H. R. -X Strong, ``Extendible Hashing - A Fast Access Method for -X Dynamic Files'', ACM Trans. Database Syst., vol. 4, -X no.3, pp. 315-344, Sept. 1979. -X -X[Wal84] -X Rich Wales, ``Discussion of "dbm" data base system'', -X USENET newsgroup unix.wizards, Jan. 1984. -X -X[Tor87] -X Chris Torek, ``Re: dbm.a and ndbm.a archives'', -X -X -X -X -X -X -X -X -X -X - 6 - -X -X -X USENET newsgroup comp.unix, 1987. -X -X[Mar79] -X G. N. Martin, ``Spiral Storage: Incrementally Augment- -X able Hash Addressed Storage'', Technical Report #27, -X University of Varwick, Coventry, U.K., 1979. -X -X[Enb88] -X R. J. Enbody and H. C. Du, ``Dynamic Hashing -X Schemes'',ACM Computing Surveys, vol. 20, no. 2, pp. -X 85-113, June 1988. -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -X -END_OF_FILE -if test 11457 -ne `wc -c <'README'`; then - echo shar: \"'README'\" unpacked with wrong size! -fi -# end of 'README' -fi -if test -f 'biblio' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'biblio'\" -else -echo shar: Extracting \"'biblio'\" \(1012 characters\) -sed "s/^X//" >'biblio' <<'END_OF_FILE' -X%A R. J. Enbody -X%A H. C. Du -X%T Dynamic Hashing Schemes -X%J ACM Computing Surveys -X%V 20 -X%N 2 -X%D June 1988 -X%P 85-113 -X%K surveys -X -X%A P.-A. Larson -X%T Dynamic Hashing -X%J BIT -X%V 18 -X%P 184-201 -X%D 1978 -X%K dynamic -X -X%A W. Litwin -X%T Linear Hashing: A new tool for file and table addressing -X%J Proceedings of the 6th Conference on Very Large Dabatases (Montreal) -X%I Very Large Database Foundation -X%C Saratoga, Calif. -X%P 212-223 -X%D 1980 -X%K linear -X -X%A R. Fagin -X%A J. Nievergelt -X%A N. Pippinger -X%A H. R. Strong -X%T Extendible Hashing - A Fast Access Method for Dynamic Files -X%J ACM Trans. Database Syst. -X%V 4 -X%N 3 -X%D Sept. 1979 -X%P 315-344 -X%K extend -X -X%A G. N. Martin -X%T Spiral Storage: Incrementally Augmentable Hash Addressed Storage -X%J Technical Report #27 -X%I University of Varwick -X%C Coventry, U.K. -X%D 1979 -X%K spiral -X -X%A Chris Torek -X%T Re: dbm.a and ndbm.a archives -X%B USENET newsgroup comp.unix -X%D 1987 -X%K torek -X -X%A Rich Wales -X%T Discusson of "dbm" data base system -X%B USENET newsgroup unix.wizards -X%D Jan. 1984 -X%K rich -X -X -X -X -X -X -END_OF_FILE -if test 1012 -ne `wc -c <'biblio'`; then - echo shar: \"'biblio'\" unpacked with wrong size! -fi -# end of 'biblio' -fi -if test -f 'dba.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'dba.c'\" -else -echo shar: Extracting \"'dba.c'\" \(1273 characters\) -sed "s/^X//" >'dba.c' <<'END_OF_FILE' -X/* -X * dba dbm analysis/recovery -X */ -X -X#include <stdio.h> -X#include <sys/file.h> -X#include "sdbm.h" -X -Xchar *progname; -Xextern void oops(); -X -Xint -Xmain(argc, argv) -Xchar **argv; -X{ -X int n; -X char *p; -X char *name; -X int pagf; -X -X progname = argv[0]; -X -X if (p = argv[1]) { -X name = (char *) malloc((n = strlen(p)) + 5); -X strcpy(name, p); -X strcpy(name + n, ".pag"); -X -X if ((pagf = open(name, O_RDONLY)) < 0) -X oops("cannot open %s.", name); -X -X sdump(pagf); -X } -X else -X oops("usage: %s dbname", progname); -X -X return 0; -X} -X -Xsdump(pagf) -Xint pagf; -X{ -X register b; -X register n = 0; -X register t = 0; -X register o = 0; -X register e; -X char pag[PBLKSIZ]; -X -X while ((b = read(pagf, pag, PBLKSIZ)) > 0) { -X printf("#%d: ", n); -X if (!okpage(pag)) -X printf("bad\n"); -X else { -X printf("ok. "); -X if (!(e = pagestat(pag))) -X o++; -X else -X t += e; -X } -X n++; -X } -X -X if (b == 0) -X printf("%d pages (%d holes): %d entries\n", n, o, t); -X else -X oops("read failed: block %d", n); -X} -X -Xpagestat(pag) -Xchar *pag; -X{ -X register n; -X register free; -X register short *ino = (short *) pag; -X -X if (!(n = ino[0])) -X printf("no entries.\n"); -X else { -X free = ino[n] - (n + 1) * sizeof(short); -X printf("%3d entries %2d%% used free %d.\n", -X n / 2, ((PBLKSIZ - free) * 100) / PBLKSIZ, free); -X } -X return n / 2; -X} -END_OF_FILE -if test 1273 -ne `wc -c <'dba.c'`; then - echo shar: \"'dba.c'\" unpacked with wrong size! -fi -# end of 'dba.c' -fi -if test -f 'dbd.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'dbd.c'\" -else -echo shar: Extracting \"'dbd.c'\" \(1719 characters\) -sed "s/^X//" >'dbd.c' <<'END_OF_FILE' -X/* -X * dbd - dump a dbm data file -X */ -X -X#include <stdio.h> -X#include <sys/file.h> -X#include "sdbm.h" -X -Xchar *progname; -Xextern void oops(); -X -X -X#define empty(page) (((short *) page)[0] == 0) -X -Xint -Xmain(argc, argv) -Xchar **argv; -X{ -X int n; -X char *p; -X char *name; -X int pagf; -X -X progname = argv[0]; -X -X if (p = argv[1]) { -X name = (char *) malloc((n = strlen(p)) + 5); -X strcpy(name, p); -X strcpy(name + n, ".pag"); -X -X if ((pagf = open(name, O_RDONLY)) < 0) -X oops("cannot open %s.", name); -X -X sdump(pagf); -X } -X else -X oops("usage: %s dbname", progname); -X return 0; -X} -X -Xsdump(pagf) -Xint pagf; -X{ -X register r; -X register n = 0; -X register o = 0; -X char pag[PBLKSIZ]; -X -X while ((r = read(pagf, pag, PBLKSIZ)) > 0) { -X if (!okpage(pag)) -X fprintf(stderr, "%d: bad page.\n", n); -X else if (empty(pag)) -X o++; -X else -X dispage(pag); -X n++; -X } -X -X if (r == 0) -X fprintf(stderr, "%d pages (%d holes).\n", n, o); -X else -X oops("read failed: block %d", n); -X} -X -X -X#ifdef OLD -Xdispage(pag) -Xchar *pag; -X{ -X register i, n; -X register off; -X register short *ino = (short *) pag; -X -X off = PBLKSIZ; -X for (i = 1; i < ino[0]; i += 2) { -X printf("\t[%d]: ", ino[i]); -X for (n = ino[i]; n < off; n++) -X putchar(pag[n]); -X putchar(' '); -X off = ino[i]; -X printf("[%d]: ", ino[i + 1]); -X for (n = ino[i + 1]; n < off; n++) -X putchar(pag[n]); -X off = ino[i + 1]; -X putchar('\n'); -X } -X} -X#else -Xdispage(pag) -Xchar *pag; -X{ -X register i, n; -X register off; -X register short *ino = (short *) pag; -X -X off = PBLKSIZ; -X for (i = 1; i < ino[0]; i += 2) { -X for (n = ino[i]; n < off; n++) -X if (pag[n] != 0) -X putchar(pag[n]); -X putchar('\t'); -X off = ino[i]; -X for (n = ino[i + 1]; n < off; n++) -X if (pag[n] != 0) -X putchar(pag[n]); -X putchar('\n'); -X off = ino[i + 1]; -X } -X} -X#endif -END_OF_FILE -if test 1719 -ne `wc -c <'dbd.c'`; then - echo shar: \"'dbd.c'\" unpacked with wrong size! -fi -# end of 'dbd.c' -fi -if test -f 'dbe.1' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'dbe.1'\" -else -echo shar: Extracting \"'dbe.1'\" \(1454 characters\) -sed "s/^X//" >'dbe.1' <<'END_OF_FILE' -X.TH dbe 1 "ndbm(3) EDITOR" -X.SH NAME -Xdbe \- Edit a ndbm(3) database -X.SH USAGE -Xdbe <database> [-m r|w|rw] [-crtvx] -a|-d|-f|-F|-s [<key> [<content>]] -X.SH DESCRIPTION -X\fIdbme\fP operates on ndbm(3) databases. -XIt can be used to create them, look at them or change them. -XWhen specifying the value of a key or the content of its associated entry, -X\\nnn, \\0, \\n, \\t, \\f and \\r are interpreted as usual. -XWhen displaying key/content pairs, non-printable characters are displayed -Xusing the \\nnn notation. -X.SH OPTIONS -X.IP -a -XList all entries in the database. -X.IP -c -XCreate the database if it does not exist. -X.IP -d -XDelete the entry associated with the specified key. -X.IP -f -XFetch and display the entry associated with the specified key. -X.IP -F -XFetch and display all the entries whose key match the specified -Xregular-expression -X.IP "-m r|w|rw" -XOpen the database in read-only, write-only or read-write mode -X.IP -r -XReplace the entry associated with the specified key if it already exists. -XSee option -s. -X.IP -s -XStore an entry under a specific key. -XAn error occurs if the key already exists and the option -r was not specified. -X.IP -t -XRe-initialize the database before executing the command. -X.IP -v -XVerbose mode. -XConfirm stores and deletions. -X.IP -x -XIf option -x is used with option -c, then if the database already exists, -Xan error occurs. -XThis can be used to implement a simple exclusive access locking mechanism. -X.SH SEE ALSO -Xndbm(3) -X.SH AUTHOR -Xjanick@bnr.ca -X -END_OF_FILE -if test 1454 -ne `wc -c <'dbe.1'`; then - echo shar: \"'dbe.1'\" unpacked with wrong size! -fi -# end of 'dbe.1' -fi -if test -f 'dbe.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'dbe.c'\" -else -echo shar: Extracting \"'dbe.c'\" \(9799 characters\) -sed "s/^X//" >'dbe.c' <<'END_OF_FILE' -X#include <stdio.h> -X#ifndef VMS -X#include <sys/file.h> -X#include <ndbm.h> -X#else -X#include "file.h" -X#include "ndbm.h" -X#endif -X#include <ctype.h> -X -X/***************************************************************************\ -X** ** -X** Function name: getopt() ** -X** Author: Henry Spencer, UofT ** -X** Coding date: 84/04/28 ** -X** ** -X** Description: ** -X** ** -X** Parses argv[] for arguments. ** -X** Works with Whitesmith's C compiler. ** -X** ** -X** Inputs - The number of arguments ** -X** - The base address of the array of arguments ** -X** - A string listing the valid options (':' indicates an ** -X** argument to the preceding option is required, a ';' ** -X** indicates an argument to the preceding option is optional) ** -X** ** -X** Outputs - Returns the next option character, ** -X** '?' for non '-' arguments ** -X** or ':' when there is no more arguments. ** -X** ** -X** Side Effects + The argument to an option is pointed to by 'optarg' ** -X** ** -X***************************************************************************** -X** ** -X** REVISION HISTORY: ** -X** ** -X** DATE NAME DESCRIPTION ** -X** YY/MM/DD ------------------ ------------------------------------ ** -X** 88/10/20 Janick Bergeron Returns '?' on unamed arguments ** -X** returns '!' on unknown options ** -X** and 'EOF' only when exhausted. ** -X** 88/11/18 Janick Bergeron Return ':' when no more arguments ** -X** 89/08/11 Janick Bergeron Optional optarg when ';' in optstring ** -X** ** -X\***************************************************************************/ -X -Xchar *optarg; /* Global argument pointer. */ -X -X#ifdef VMS -X#define index strchr -X#endif -X -Xchar -Xgetopt(argc, argv, optstring) -Xint argc; -Xchar **argv; -Xchar *optstring; -X{ -X register int c; -X register char *place; -X extern char *index(); -X static int optind = 0; -X static char *scan = NULL; -X -X optarg = NULL; -X -X if (scan == NULL || *scan == '\0') { -X -X if (optind == 0) -X optind++; -X if (optind >= argc) -X return ':'; -X -X optarg = place = argv[optind++]; -X if (place[0] != '-' || place[1] == '\0') -X return '?'; -X if (place[1] == '-' && place[2] == '\0') -X return '?'; -X scan = place + 1; -X } -X -X c = *scan++; -X place = index(optstring, c); -X if (place == NULL || c == ':' || c == ';') { -X -X (void) fprintf(stderr, "%s: unknown option %c\n", argv[0], c); -X scan = NULL; -X return '!'; -X } -X if (*++place == ':') { -X -X if (*scan != '\0') { -X -X optarg = scan; -X scan = NULL; -X -X } -X else { -X -X if (optind >= argc) { -X -X (void) fprintf(stderr, "%s: %c requires an argument\n", -X argv[0], c); -X return '!'; -X } -X optarg = argv[optind]; -X optind++; -X } -X } -X else if (*place == ';') { -X -X if (*scan != '\0') { -X -X optarg = scan; -X scan = NULL; -X -X } -X else { -X -X if (optind >= argc || *argv[optind] == '-') -X optarg = NULL; -X else { -X optarg = argv[optind]; -X optind++; -X } -X } -X } -X return c; -X} -X -X -Xvoid -Xprint_datum(db) -Xdatum db; -X{ -X int i; -X -X putchar('"'); -X for (i = 0; i < db.dsize; i++) { -X if (isprint(db.dptr[i])) -X putchar(db.dptr[i]); -X else { -X putchar('\\'); -X putchar('0' + ((db.dptr[i] >> 6) & 0x07)); -X putchar('0' + ((db.dptr[i] >> 3) & 0x07)); -X putchar('0' + (db.dptr[i] & 0x07)); -X } -X } -X putchar('"'); -X} -X -X -Xdatum -Xread_datum(s) -Xchar *s; -X{ -X datum db; -X char *p; -X int i; -X -X db.dsize = 0; -X db.dptr = (char *) malloc(strlen(s) * sizeof(char)); -X for (p = db.dptr; *s != '\0'; p++, db.dsize++, s++) { -X if (*s == '\\') { -X if (*++s == 'n') -X *p = '\n'; -X else if (*s == 'r') -X *p = '\r'; -X else if (*s == 'f') -X *p = '\f'; -X else if (*s == 't') -X *p = '\t'; -X else if (isdigit(*s) && isdigit(*(s + 1)) && isdigit(*(s + 2))) { -X i = (*s++ - '0') << 6; -X i |= (*s++ - '0') << 3; -X i |= *s - '0'; -X *p = i; -X } -X else if (*s == '0') -X *p = '\0'; -X else -X *p = *s; -X } -X else -X *p = *s; -X } -X -X return db; -X} -X -X -Xchar * -Xkey2s(db) -Xdatum db; -X{ -X char *buf; -X char *p1, *p2; -X -X buf = (char *) malloc((db.dsize + 1) * sizeof(char)); -X for (p1 = buf, p2 = db.dptr; *p2 != '\0'; *p1++ = *p2++); -X *p1 = '\0'; -X return buf; -X} -X -X -Xmain(argc, argv) -Xint argc; -Xchar **argv; -X{ -X typedef enum { -X YOW, FETCH, STORE, DELETE, SCAN, REGEXP -X } commands; -X char opt; -X int flags; -X int giveusage = 0; -X int verbose = 0; -X commands what = YOW; -X char *comarg[3]; -X int st_flag = DBM_INSERT; -X int argn; -X DBM *db; -X datum key; -X datum content; -X -X flags = O_RDWR; -X argn = 0; -X -X while ((opt = getopt(argc, argv, "acdfFm:rstvx")) != ':') { -X switch (opt) { -X case 'a': -X what = SCAN; -X break; -X case 'c': -X flags |= O_CREAT; -X break; -X case 'd': -X what = DELETE; -X break; -X case 'f': -X what = FETCH; -X break; -X case 'F': -X what = REGEXP; -X break; -X case 'm': -X flags &= ~(000007); -X if (strcmp(optarg, "r") == 0) -X flags |= O_RDONLY; -X else if (strcmp(optarg, "w") == 0) -X flags |= O_WRONLY; -X else if (strcmp(optarg, "rw") == 0) -X flags |= O_RDWR; -X else { -X fprintf(stderr, "Invalid mode: \"%s\"\n", optarg); -X giveusage = 1; -X } -X break; -X case 'r': -X st_flag = DBM_REPLACE; -X break; -X case 's': -X what = STORE; -X break; -X case 't': -X flags |= O_TRUNC; -X break; -X case 'v': -X verbose = 1; -X break; -X case 'x': -X flags |= O_EXCL; -X break; -X case '!': -X giveusage = 1; -X break; -X case '?': -X if (argn < 3) -X comarg[argn++] = optarg; -X else { -X fprintf(stderr, "Too many arguments.\n"); -X giveusage = 1; -X } -X break; -X } -X } -X -X if (giveusage | what == YOW | argn < 1) { -X fprintf(stderr, "Usage: %s databse [-m r|w|rw] [-crtx] -a|-d|-f|-F|-s [key [content]]\n", argv[0]); -X exit(-1); -X } -X -X if ((db = dbm_open(comarg[0], flags, 0777)) == NULL) { -X fprintf(stderr, "Error opening database \"%s\"\n", comarg[0]); -X exit(-1); -X } -X -X if (argn > 1) -X key = read_datum(comarg[1]); -X if (argn > 2) -X content = read_datum(comarg[2]); -X -X switch (what) { -X -X case SCAN: -X key = dbm_firstkey(db); -X if (dbm_error(db)) { -X fprintf(stderr, "Error when fetching first key\n"); -X goto db_exit; -X } -X while (key.dptr != NULL) { -X content = dbm_fetch(db, key); -X if (dbm_error(db)) { -X fprintf(stderr, "Error when fetching "); -X print_datum(key); -X printf("\n"); -X goto db_exit; -X } -X print_datum(key); -X printf(": "); -X print_datum(content); -X printf("\n"); -X if (dbm_error(db)) { -X fprintf(stderr, "Error when fetching next key\n"); -X goto db_exit; -X } -X key = dbm_nextkey(db); -X } -X break; -X -X case REGEXP: -X if (argn < 2) { -X fprintf(stderr, "Missing regular expression.\n"); -X goto db_exit; -X } -X if (re_comp(comarg[1])) { -X fprintf(stderr, "Invalid regular expression\n"); -X goto db_exit; -X } -X key = dbm_firstkey(db); -X if (dbm_error(db)) { -X fprintf(stderr, "Error when fetching first key\n"); -X goto db_exit; -X } -X while (key.dptr != NULL) { -X if (re_exec(key2s(key))) { -X content = dbm_fetch(db, key); -X if (dbm_error(db)) { -X fprintf(stderr, "Error when fetching "); -X print_datum(key); -X printf("\n"); -X goto db_exit; -X } -X print_datum(key); -X printf(": "); -X print_datum(content); -X printf("\n"); -X if (dbm_error(db)) { -X fprintf(stderr, "Error when fetching next key\n"); -X goto db_exit; -X } -X } -X key = dbm_nextkey(db); -X } -X break; -X -X case FETCH: -X if (argn < 2) { -X fprintf(stderr, "Missing fetch key.\n"); -X goto db_exit; -X } -X content = dbm_fetch(db, key); -X if (dbm_error(db)) { -X fprintf(stderr, "Error when fetching "); -X print_datum(key); -X printf("\n"); -X goto db_exit; -X } -X if (content.dptr == NULL) { -X fprintf(stderr, "Cannot find "); -X print_datum(key); -X printf("\n"); -X goto db_exit; -X } -X print_datum(key); -X printf(": "); -X print_datum(content); -X printf("\n"); -X break; -X -X case DELETE: -X if (argn < 2) { -X fprintf(stderr, "Missing delete key.\n"); -X goto db_exit; -X } -X if (dbm_delete(db, key) || dbm_error(db)) { -X fprintf(stderr, "Error when deleting "); -X print_datum(key); -X printf("\n"); -X goto db_exit; -X } -X if (verbose) { -X print_datum(key); -X printf(": DELETED\n"); -X } -X break; -X -X case STORE: -X if (argn < 3) { -X fprintf(stderr, "Missing key and/or content.\n"); -X goto db_exit; -X } -X if (dbm_store(db, key, content, st_flag) || dbm_error(db)) { -X fprintf(stderr, "Error when storing "); -X print_datum(key); -X printf("\n"); -X goto db_exit; -X } -X if (verbose) { -X print_datum(key); -X printf(": "); -X print_datum(content); -X printf(" STORED\n"); -X } -X break; -X } -X -Xdb_exit: -X dbm_clearerr(db); -X dbm_close(db); -X if (dbm_error(db)) { -X fprintf(stderr, "Error closing database \"%s\"\n", comarg[0]); -X exit(-1); -X } -X} -END_OF_FILE -if test 9799 -ne `wc -c <'dbe.c'`; then - echo shar: \"'dbe.c'\" unpacked with wrong size! -fi -# end of 'dbe.c' -fi -if test -f 'dbm.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'dbm.c'\" -else -echo shar: Extracting \"'dbm.c'\" \(2426 characters\) -sed "s/^X//" >'dbm.c' <<'END_OF_FILE' -X/* -X * Copyright (c) 1985 The Regents of the University of California. -X * All rights reserved. -X * -X * Redistribution and use in source and binary forms are permitted -X * provided that the above copyright notice and this paragraph are -X * duplicated in all such forms and that any documentation, -X * advertising materials, and other materials related to such -X * distribution and use acknowledge that the software was developed -X * by the University of California, Berkeley. The name of the -X * University may not be used to endorse or promote products derived -X * from this software without specific prior written permission. -X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR -X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED -X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. -X */ -X -X#ifndef lint -Xstatic char sccsid[] = "@(#)dbm.c 5.4 (Berkeley) 5/24/89"; -X#endif /* not lint */ -X -X#include "dbm.h" -X -X#define NODB ((DBM *)0) -X -Xstatic DBM *cur_db = NODB; -X -Xstatic char no_db[] = "dbm: no open database\n"; -X -Xdbminit(file) -X char *file; -X{ -X if (cur_db != NODB) -X dbm_close(cur_db); -X -X cur_db = dbm_open(file, 2, 0); -X if (cur_db == NODB) { -X cur_db = dbm_open(file, 0, 0); -X if (cur_db == NODB) -X return (-1); -X } -X return (0); -X} -X -Xlong -Xforder(key) -Xdatum key; -X{ -X if (cur_db == NODB) { -X printf(no_db); -X return (0L); -X } -X return (dbm_forder(cur_db, key)); -X} -X -Xdatum -Xfetch(key) -Xdatum key; -X{ -X datum item; -X -X if (cur_db == NODB) { -X printf(no_db); -X item.dptr = 0; -X return (item); -X } -X return (dbm_fetch(cur_db, key)); -X} -X -Xdelete(key) -Xdatum key; -X{ -X if (cur_db == NODB) { -X printf(no_db); -X return (-1); -X } -X if (dbm_rdonly(cur_db)) -X return (-1); -X return (dbm_delete(cur_db, key)); -X} -X -Xstore(key, dat) -Xdatum key, dat; -X{ -X if (cur_db == NODB) { -X printf(no_db); -X return (-1); -X } -X if (dbm_rdonly(cur_db)) -X return (-1); -X -X return (dbm_store(cur_db, key, dat, DBM_REPLACE)); -X} -X -Xdatum -Xfirstkey() -X{ -X datum item; -X -X if (cur_db == NODB) { -X printf(no_db); -X item.dptr = 0; -X return (item); -X } -X return (dbm_firstkey(cur_db)); -X} -X -Xdatum -Xnextkey(key) -Xdatum key; -X{ -X datum item; -X -X if (cur_db == NODB) { -X printf(no_db); -X item.dptr = 0; -X return (item); -X } -X return (dbm_nextkey(cur_db, key)); -X} -END_OF_FILE -if test 2426 -ne `wc -c <'dbm.c'`; then - echo shar: \"'dbm.c'\" unpacked with wrong size! -fi -# end of 'dbm.c' -fi -if test -f 'dbm.h' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'dbm.h'\" -else -echo shar: Extracting \"'dbm.h'\" \(1186 characters\) -sed "s/^X//" >'dbm.h' <<'END_OF_FILE' -X/* -X * Copyright (c) 1983 The Regents of the University of California. -X * All rights reserved. -X * -X * Redistribution and use in source and binary forms are permitted -X * provided that the above copyright notice and this paragraph are -X * duplicated in all such forms and that any documentation, -X * advertising materials, and other materials related to such -X * distribution and use acknowledge that the software was developed -X * by the University of California, Berkeley. The name of the -X * University may not be used to endorse or promote products derived -X * from this software without specific prior written permission. -X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR -X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED -X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. -X * -X * @(#)dbm.h 5.2 (Berkeley) 5/24/89 -X */ -X -X#ifndef NULL -X/* -X * this is lunacy, we no longer use it (and never should have -X * unconditionally defined it), but, this whole file is for -X * backwards compatability - someone may rely on this. -X */ -X#define NULL ((char *) 0) -X#endif -X -X#include <ndbm.h> -X -Xdatum fetch(); -Xdatum firstkey(); -Xdatum nextkey(); -END_OF_FILE -if test 1186 -ne `wc -c <'dbm.h'`; then - echo shar: \"'dbm.h'\" unpacked with wrong size! -fi -# end of 'dbm.h' -fi -if test -f 'dbu.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'dbu.c'\" -else -echo shar: Extracting \"'dbu.c'\" \(4408 characters\) -sed "s/^X//" >'dbu.c' <<'END_OF_FILE' -X#include <stdio.h> -X#include <sys/file.h> -X#ifdef SDBM -X#include "sdbm.h" -X#else -X#include <ndbm.h> -X#endif -X#include <string.h> -X -X#ifdef BSD42 -X#define strchr index -X#endif -X -Xextern int getopt(); -Xextern char *strchr(); -Xextern void oops(); -X -Xchar *progname; -X -Xstatic int rflag; -Xstatic char *usage = "%s [-R] cat | look |... dbmname"; -X -X#define DERROR 0 -X#define DLOOK 1 -X#define DINSERT 2 -X#define DDELETE 3 -X#define DCAT 4 -X#define DBUILD 5 -X#define DPRESS 6 -X#define DCREAT 7 -X -X#define LINEMAX 8192 -X -Xtypedef struct { -X char *sname; -X int scode; -X int flags; -X} cmd; -X -Xstatic cmd cmds[] = { -X -X "fetch", DLOOK, O_RDONLY, -X "get", DLOOK, O_RDONLY, -X "look", DLOOK, O_RDONLY, -X "add", DINSERT, O_RDWR, -X "insert", DINSERT, O_RDWR, -X "store", DINSERT, O_RDWR, -X "delete", DDELETE, O_RDWR, -X "remove", DDELETE, O_RDWR, -X "dump", DCAT, O_RDONLY, -X "list", DCAT, O_RDONLY, -X "cat", DCAT, O_RDONLY, -X "creat", DCREAT, O_RDWR | O_CREAT | O_TRUNC, -X "new", DCREAT, O_RDWR | O_CREAT | O_TRUNC, -X "build", DBUILD, O_RDWR | O_CREAT, -X "squash", DPRESS, O_RDWR, -X "compact", DPRESS, O_RDWR, -X "compress", DPRESS, O_RDWR -X}; -X -X#define CTABSIZ (sizeof (cmds)/sizeof (cmd)) -X -Xstatic cmd *parse(); -Xstatic void badk(), doit(), prdatum(); -X -Xint -Xmain(argc, argv) -Xint argc; -Xchar *argv[]; -X{ -X int c; -X register cmd *act; -X extern int optind; -X extern char *optarg; -X -X progname = argv[0]; -X -X while ((c = getopt(argc, argv, "R")) != EOF) -X switch (c) { -X case 'R': /* raw processing */ -X rflag++; -X break; -X -X default: -X oops("usage: %s", usage); -X break; -X } -X -X if ((argc -= optind) < 2) -X oops("usage: %s", usage); -X -X if ((act = parse(argv[optind])) == NULL) -X badk(argv[optind]); -X optind++; -X doit(act, argv[optind]); -X return 0; -X} -X -Xstatic void -Xdoit(act, file) -Xregister cmd *act; -Xchar *file; -X{ -X datum key; -X datum val; -X register DBM *db; -X register char *op; -X register int n; -X char *line; -X#ifdef TIME -X long start; -X extern long time(); -X#endif -X -X if ((db = dbm_open(file, act->flags, 0644)) == NULL) -X oops("cannot open: %s", file); -X -X if ((line = (char *) malloc(LINEMAX)) == NULL) -X oops("%s: cannot get memory", "line alloc"); -X -X switch (act->scode) { -X -X case DLOOK: -X while (fgets(line, LINEMAX, stdin) != NULL) { -X n = strlen(line) - 1; -X line[n] = 0; -X key.dptr = line; -X key.dsize = n; -X val = dbm_fetch(db, key); -X if (val.dptr != NULL) { -X prdatum(stdout, val); -X putchar('\n'); -X continue; -X } -X prdatum(stderr, key); -X fprintf(stderr, ": not found.\n"); -X } -X break; -X case DINSERT: -X break; -X case DDELETE: -X while (fgets(line, LINEMAX, stdin) != NULL) { -X n = strlen(line) - 1; -X line[n] = 0; -X key.dptr = line; -X key.dsize = n; -X if (dbm_delete(db, key) == -1) { -X prdatum(stderr, key); -X fprintf(stderr, ": not found.\n"); -X } -X } -X break; -X case DCAT: -X for (key = dbm_firstkey(db); key.dptr != 0; -X key = dbm_nextkey(db)) { -X prdatum(stdout, key); -X putchar('\t'); -X prdatum(stdout, dbm_fetch(db, key)); -X putchar('\n'); -X } -X break; -X case DBUILD: -X#ifdef TIME -X start = time(0); -X#endif -X while (fgets(line, LINEMAX, stdin) != NULL) { -X n = strlen(line) - 1; -X line[n] = 0; -X key.dptr = line; -X if ((op = strchr(line, '\t')) != 0) { -X key.dsize = op - line; -X *op++ = 0; -X val.dptr = op; -X val.dsize = line + n - op; -X } -X else -X oops("bad input; %s", line); -X -X if (dbm_store(db, key, val, DBM_REPLACE) < 0) { -X prdatum(stderr, key); -X fprintf(stderr, ": "); -X oops("store: %s", "failed"); -X } -X } -X#ifdef TIME -X printf("done: %d seconds.\n", time(0) - start); -X#endif -X break; -X case DPRESS: -X break; -X case DCREAT: -X break; -X } -X -X dbm_close(db); -X} -X -Xstatic void -Xbadk(word) -Xchar *word; -X{ -X register int i; -X -X if (progname) -X fprintf(stderr, "%s: ", progname); -X fprintf(stderr, "bad keywd %s. use one of\n", word); -X for (i = 0; i < (int)CTABSIZ; i++) -X fprintf(stderr, "%-8s%c", cmds[i].sname, -X ((i + 1) % 6 == 0) ? '\n' : ' '); -X fprintf(stderr, "\n"); -X exit(1); -X /*NOTREACHED*/ -X} -X -Xstatic cmd * -Xparse(str) -Xregister char *str; -X{ -X register int i = CTABSIZ; -X register cmd *p; -X -X for (p = cmds; i--; p++) -X if (strcmp(p->sname, str) == 0) -X return p; -X return NULL; -X} -X -Xstatic void -Xprdatum(stream, d) -XFILE *stream; -Xdatum d; -X{ -X register int c; -X register char *p = d.dptr; -X register int n = d.dsize; -X -X while (n--) { -X c = *p++ & 0377; -X if (c & 0200) { -X fprintf(stream, "M-"); -X c &= 0177; -X } -X if (c == 0177 || c < ' ') -X fprintf(stream, "^%c", (c == 0177) ? '?' : c + '@'); -X else -X putc(c, stream); -X } -X} -X -X -END_OF_FILE -if test 4408 -ne `wc -c <'dbu.c'`; then - echo shar: \"'dbu.c'\" unpacked with wrong size! -fi -# end of 'dbu.c' -fi -if test -f 'grind' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'grind'\" -else -echo shar: Extracting \"'grind'\" \(201 characters\) -sed "s/^X//" >'grind' <<'END_OF_FILE' -X#!/bin/sh -Xrm -f /tmp/*.dir /tmp/*.pag -Xawk -e '{ -X printf "%s\t", $0 -X for (i = 0; i < 40; i++) -X printf "%s.", $0 -X printf "\n" -X}' < /usr/dict/words | $1 build /tmp/$2 -X -END_OF_FILE -if test 201 -ne `wc -c <'grind'`; then - echo shar: \"'grind'\" unpacked with wrong size! -fi -chmod +x 'grind' -# end of 'grind' -fi -if test -f 'hash.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'hash.c'\" -else -echo shar: Extracting \"'hash.c'\" \(922 characters\) -sed "s/^X//" >'hash.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. keep it that way. -X * -X * hashing routine -X */ -X -X#include "sdbm.h" -X/* -X * polynomial conversion ignoring overflows -X * [this seems to work remarkably well, in fact better -X * then the ndbm hash function. Replace at your own risk] -X * use: 65599 nice. -X * 65587 even better. -X */ -Xlong -Xdbm_hash(str, len) -Xregister char *str; -Xregister int len; -X{ -X register unsigned long n = 0; -X -X#ifdef DUFF -X -X#define HASHC n = *str++ + 65599 * n -X -X if (len > 0) { -X register int loop = (len + 8 - 1) >> 3; -X -X switch(len & (8 - 1)) { -X case 0: do { -X HASHC; case 7: HASHC; -X case 6: HASHC; case 5: HASHC; -X case 4: HASHC; case 3: HASHC; -X case 2: HASHC; case 1: HASHC; -X } while (--loop); -X } -X -X } -X#else -X while (len--) -X n = *str++ + 65599 * n; -X#endif -X return n; -X} -END_OF_FILE -if test 922 -ne `wc -c <'hash.c'`; then - echo shar: \"'hash.c'\" unpacked with wrong size! -fi -# end of 'hash.c' -fi -if test -f 'makefile' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'makefile'\" -else -echo shar: Extracting \"'makefile'\" \(1147 characters\) -sed "s/^X//" >'makefile' <<'END_OF_FILE' -X# -X# makefile for public domain ndbm-clone: sdbm -X# DUFF: use duff's device (loop unroll) in parts of the code -X# -XCFLAGS = -O -DSDBM -DDUFF -DBSD42 -X#LDFLAGS = -p -X -XOBJS = sdbm.o pair.o hash.o -XSRCS = sdbm.c pair.c hash.c dbu.c dba.c dbd.c util.c -XHDRS = tune.h sdbm.h pair.h -XMISC = README CHANGES COMPARE sdbm.3 dbe.c dbe.1 dbm.c dbm.h biblio \ -X readme.ms readme.ps -X -Xall: dbu dba dbd dbe -X -Xdbu: dbu.o sdbm util.o -X cc $(LDFLAGS) -o dbu dbu.o util.o libsdbm.a -X -Xdba: dba.o util.o -X cc $(LDFLAGS) -o dba dba.o util.o -Xdbd: dbd.o util.o -X cc $(LDFLAGS) -o dbd dbd.o util.o -Xdbe: dbe.o sdbm -X cc $(LDFLAGS) -o dbe dbe.o libsdbm.a -X -Xsdbm: $(OBJS) -X ar cr libsdbm.a $(OBJS) -X ranlib libsdbm.a -X### cp libsdbm.a /usr/lib/libsdbm.a -X -Xdba.o: sdbm.h -Xdbu.o: sdbm.h -Xutil.o:sdbm.h -X -X$(OBJS): sdbm.h tune.h pair.h -X -X# -X# dbu using berkelezoid ndbm routines [if you have them] for testing -X# -X#x-dbu: dbu.o util.o -X# cc $(CFLAGS) -o x-dbu dbu.o util.o -Xlint: -X lint -abchx $(SRCS) -X -Xclean: -X rm -f *.o mon.out core -X -Xpurge: clean -X rm -f dbu libsdbm.a dbd dba dbe x-dbu *.dir *.pag -X -Xshar: -X shar $(MISC) makefile $(SRCS) $(HDRS) >SDBM.SHAR -X -Xreadme: -X nroff -ms readme.ms | col -b >README -END_OF_FILE -if test 1147 -ne `wc -c <'makefile'`; then - echo shar: \"'makefile'\" unpacked with wrong size! -fi -# end of 'makefile' -fi -if test -f 'pair.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'pair.c'\" -else -echo shar: Extracting \"'pair.c'\" \(5720 characters\) -sed "s/^X//" >'pair.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 * page-level routines -X */ -X -X#ifndef lint -Xstatic char rcsid[] = "$Id: pair.c,v 1.10 90/12/13 13:00:35 oz Exp $"; -X#endif -X -X#include "sdbm.h" -X#include "tune.h" -X#include "pair.h" -X -X#ifndef BSD42 -X#include <memory.h> -X#endif -X -X#define exhash(item) dbm_hash((item).dptr, (item).dsize) -X -X/* -X * forward -X */ -Xstatic int seepair proto((char *, int, char *, int)); -X -X/* -X * page format: -X * +------------------------------+ -X * ino | n | keyoff | datoff | keyoff | -X * +------------+--------+--------+ -X * | datoff | - - - ----> | -X * +--------+---------------------+ -X * | F R E E A R E A | -X * +--------------+---------------+ -X * | <---- - - - | data | -X * +--------+-----+----+----------+ -X * | key | data | key | -X * +--------+----------+----------+ -X * -X * calculating the offsets for free area: if the number -X * of entries (ino[0]) is zero, the offset to the END of -X * the free area is the block size. Otherwise, it is the -X * nth (ino[ino[0]]) entry's offset. -X */ -X -Xint -Xfitpair(pag, need) -Xchar *pag; -Xint need; -X{ -X register int n; -X register int off; -X register int free; -X register short *ino = (short *) pag; -X -X off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; -X free = off - (n + 1) * sizeof(short); -X need += 2 * sizeof(short); -X -X debug(("free %d need %d\n", free, need)); -X -X return need <= free; -X} -X -Xvoid -Xputpair(pag, key, val) -Xchar *pag; -Xdatum key; -Xdatum val; -X{ -X register int n; -X register int off; -X register short *ino = (short *) pag; -X -X off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; -X/* -X * enter the key first -X */ -X off -= key.dsize; -X (void) memcpy(pag + off, key.dptr, key.dsize); -X ino[n + 1] = off; -X/* -X * now the data -X */ -X off -= val.dsize; -X (void) memcpy(pag + off, val.dptr, val.dsize); -X ino[n + 2] = off; -X/* -X * adjust item count -X */ -X ino[0] += 2; -X} -X -Xdatum -Xgetpair(pag, key) -Xchar *pag; -Xdatum key; -X{ -X register int i; -X register int n; -X datum val; -X register short *ino = (short *) pag; -X -X if ((n = ino[0]) == 0) -X return nullitem; -X -X if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) -X return nullitem; -X -X val.dptr = pag + ino[i + 1]; -X val.dsize = ino[i] - ino[i + 1]; -X return val; -X} -X -X#ifdef SEEDUPS -Xint -Xduppair(pag, key) -Xchar *pag; -Xdatum key; -X{ -X register short *ino = (short *) pag; -X return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; -X} -X#endif -X -Xdatum -Xgetnkey(pag, num) -Xchar *pag; -Xint num; -X{ -X datum key; -X register int off; -X register short *ino = (short *) pag; -X -X num = num * 2 - 1; -X if (ino[0] == 0 || num > ino[0]) -X return nullitem; -X -X off = (num > 1) ? ino[num - 1] : PBLKSIZ; -X -X key.dptr = pag + ino[num]; -X key.dsize = off - ino[num]; -X -X return key; -X} -X -Xint -Xdelpair(pag, key) -Xchar *pag; -Xdatum key; -X{ -X register int n; -X register int i; -X register short *ino = (short *) pag; -X -X if ((n = ino[0]) == 0) -X return 0; -X -X if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) -X return 0; -X/* -X * found the key. if it is the last entry -X * [i.e. i == n - 1] we just adjust the entry count. -X * hard case: move all data down onto the deleted pair, -X * shift offsets onto deleted offsets, and adjust them. -X * [note: 0 < i < n] -X */ -X if (i < n - 1) { -X register int m; -X register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]); -X register char *src = pag + ino[i + 1]; -X register int zoo = dst - src; -X -X debug(("free-up %d ", zoo)); -X/* -X * shift data/keys down -X */ -X m = ino[i + 1] - ino[n]; -X#ifdef DUFF -X#define MOVB *--dst = *--src -X -X if (m > 0) { -X register int loop = (m + 8 - 1) >> 3; -X -X switch (m & (8 - 1)) { -X case 0: do { -X MOVB; case 7: MOVB; -X case 6: MOVB; case 5: MOVB; -X case 4: MOVB; case 3: MOVB; -X case 2: MOVB; case 1: MOVB; -X } while (--loop); -X } -X } -X#else -X#ifdef MEMMOVE -X memmove(dst, src, m); -X#else -X while (m--) -X *--dst = *--src; -X#endif -X#endif -X/* -X * adjust offset index up -X */ -X while (i < n - 1) { -X ino[i] = ino[i + 2] + zoo; -X i++; -X } -X } -X ino[0] -= 2; -X return 1; -X} -X -X/* -X * search for the key in the page. -X * return offset index in the range 0 < i < n. -X * return 0 if not found. -X */ -Xstatic int -Xseepair(pag, n, key, siz) -Xchar *pag; -Xregister int n; -Xregister char *key; -Xregister int siz; -X{ -X register int i; -X register int off = PBLKSIZ; -X register short *ino = (short *) pag; -X -X for (i = 1; i < n; i += 2) { -X if (siz == off - ino[i] && -X memcmp(key, pag + ino[i], siz) == 0) -X return i; -X off = ino[i + 1]; -X } -X return 0; -X} -X -Xvoid -Xsplpage(pag, new, sbit) -Xchar *pag; -Xchar *new; -Xlong sbit; -X{ -X datum key; -X datum val; -X -X register int n; -X register int off = PBLKSIZ; -X char cur[PBLKSIZ]; -X register short *ino = (short *) cur; -X -X (void) memcpy(cur, pag, PBLKSIZ); -X (void) memset(pag, 0, PBLKSIZ); -X (void) memset(new, 0, PBLKSIZ); -X -X n = ino[0]; -X for (ino++; n > 0; ino += 2) { -X key.dptr = cur + ino[0]; -X key.dsize = off - ino[0]; -X val.dptr = cur + ino[1]; -X val.dsize = ino[0] - ino[1]; -X/* -X * select the page pointer (by looking at sbit) and insert -X */ -X (void) putpair((exhash(key) & sbit) ? new : pag, key, val); -X -X off = ino[1]; -X n -= 2; -X } -X -X debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, -X ((short *) new)[0] / 2, -X ((short *) pag)[0] / 2)); -X} -X -X/* -X * check page sanity: -X * number of entries should be something -X * reasonable, and all offsets in the index should be in order. -X * this could be made more rigorous. -X */ -Xint -Xchkpage(pag) -Xchar *pag; -X{ -X register int n; -X register int off; -X register short *ino = (short *) pag; -X -X if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short)) -X return 0; -X -X if (n > 0) { -X off = PBLKSIZ; -X for (ino++; n > 0; ino += 2) { -X if (ino[0] > off || ino[1] > off || -X ino[1] > ino[0]) -X return 0; -X off = ino[1]; -X n -= 2; -X } -X } -X return 1; -X} -END_OF_FILE -if test 5720 -ne `wc -c <'pair.c'`; then - echo shar: \"'pair.c'\" unpacked with wrong size! -fi -# end of 'pair.c' -fi -if test -f 'pair.h' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'pair.h'\" -else -echo shar: Extracting \"'pair.h'\" \(378 characters\) -sed "s/^X//" >'pair.h' <<'END_OF_FILE' -Xextern int fitpair proto((char *, int)); -Xextern void putpair proto((char *, datum, datum)); -Xextern datum getpair proto((char *, datum)); -Xextern int delpair proto((char *, datum)); -Xextern int chkpage proto((char *)); -Xextern datum getnkey proto((char *, int)); -Xextern void splpage proto((char *, char *, long)); -X#ifdef SEEDUPS -Xextern int duppair proto((char *, datum)); -X#endif -END_OF_FILE -if test 378 -ne `wc -c <'pair.h'`; then - echo shar: \"'pair.h'\" unpacked with wrong size! -fi -# end of 'pair.h' -fi -if test -f 'readme.ms' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'readme.ms'\" -else -echo shar: Extracting \"'readme.ms'\" \(11691 characters\) -sed "s/^X//" >'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 <'readme.ms'`; then - echo shar: \"'readme.ms'\" unpacked with wrong size! -fi -# end of 'readme.ms' -fi -if test -f 'readme.ps' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'readme.ps'\" -else -echo shar: Extracting \"'readme.ps'\" \(33302 characters\) -sed "s/^X//" >'readme.ps' <<'END_OF_FILE' -X%!PS-Adobe-1.0 -X%%Creator: yetti:oz (Ozan Yigit) -X%%Title: stdin (ditroff) -X%%CreationDate: Thu Dec 13 15:56:08 1990 -X%%EndComments -X% lib/psdit.pro -- prolog for psdit (ditroff) files -X% Copyright (c) 1984, 1985 Adobe Systems Incorporated. All Rights Reserved. -X% last edit: shore Sat Nov 23 20:28:03 1985 -X% RCSID: $Header: psdit.pro,v 2.1 85/11/24 12:19:43 shore Rel $ -X -X/$DITroff 140 dict def $DITroff begin -X/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def -X/xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto -X /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F -X /pagesave save def}def -X/PB{save /psv exch def currentpoint translate -X resolution 72 div dup neg scale 0 0 moveto}def -X/PE{psv restore}def -X/arctoobig 90 def /arctoosmall .05 def -X/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def -X/tan{dup sin exch cos div}def -X/point{resolution 72 div mul}def -X/dround {transform round exch round exch itransform}def -X/xT{/devname exch def}def -X/xr{/mh exch def /my exch def /resolution exch def}def -X/xp{}def -X/xs{docsave restore end}def -X/xt{}def -X/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not -X {fonts slotno fontname findfont put fontnames slotno fontname put}if}def -X/xH{/fontheight exch def F}def -X/xS{/fontslant exch def F}def -X/s{/fontsize exch def /fontheight fontsize def F}def -X/f{/fontnum exch def F}def -X/F{fontheight 0 le {/fontheight fontsize def}if -X fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore -X fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if -X makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def -X/X{exch currentpoint exch pop moveto show}def -X/N{3 1 roll moveto show}def -X/Y{exch currentpoint pop exch moveto show}def -X/S{show}def -X/ditpush{}def/ditpop{}def -X/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def -X/AN{4 2 roll moveto 0 exch ashow}def -X/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def -X/AS{0 exch ashow}def -X/MX{currentpoint exch pop moveto}def -X/MY{currentpoint pop exch moveto}def -X/MXY{moveto}def -X/cb{pop}def % action on unknown char -- nothing for now -X/n{}def/w{}def -X/p{pop showpage pagesave restore /pagesave save def}def -X/abspoint{currentpoint exch pop add exch currentpoint pop add exch}def -X/distance{dup mul exch dup mul add sqrt}def -X/dstroke{currentpoint stroke moveto}def -X/Dl{2 copy gsave rlineto stroke grestore rmoveto}def -X/arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop -X currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def -X currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def -X/Dc{dup arcellipse dstroke}def -X/De{arcellipse dstroke}def -X/Da{/endv exch def /endh exch def /centerv exch def /centerh exch def -X /cradius centerv centerv mul centerh centerh mul add sqrt def -X /eradius endv endv mul endh endh mul add sqrt def -X /endang endv endh atan def -X /startang centerv neg centerh neg atan def -X /sweep startang endang sub dup 0 lt{360 add}if def -X sweep arctoobig gt -X {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def -X /midh midang cos midrad mul def /midv midang sin midrad mul def -X midh neg midv neg endh endv centerh centerv midh midv Da -X currentpoint moveto Da} -X {sweep arctoosmall ge -X {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def -X centerv neg controldelt mul centerh controldelt mul -X endv neg controldelt mul centerh add endh add -X endh controldelt mul centerv add endv add -X centerh endh add centerv endv add rcurveto dstroke} -X {centerh endh add centerv endv add rlineto dstroke}ifelse}ifelse}def -X -X/Barray 200 array def % 200 values in a wiggle -X/D~{mark}def -X/D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop -X /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and -X {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def -X Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put -X Bcontrol Blen 2 sub 2 copy get 2 mul put -X Bcontrol Blen 1 sub 2 copy get 2 mul put -X /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub -X {/i exch def -X Bcontrol i get 3 div Bcontrol i 1 add get 3 div -X Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div -X Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div -X /Xbi Xcont Bcontrol i 2 add get 2 div add def -X /Ybi Ycont Bcontrol i 3 add get 2 div add def -X /Xcont Xcont Bcontrol i 2 add get add def -X /Ycont Ycont Bcontrol i 3 add get add def -X Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto -X }for dstroke}if}def -Xend -X/ditstart{$DITroff begin -X /nfonts 60 def % NFONTS makedev/ditroff dependent! -X /fonts[nfonts{0}repeat]def -X /fontnames[nfonts{()}repeat]def -X/docsave save def -X}def -X -X% character outcalls -X/oc {/pswid exch def /cc exch def /name exch def -X /ditwid pswid fontsize mul resolution mul 72000 div def -X /ditsiz fontsize resolution mul 72 div def -X ocprocs name known{ocprocs name get exec}{name cb} -X ifelse}def -X/fractm [.65 0 0 .6 0 0] def -X/fraction -X {/fden exch def /fnum exch def gsave /cf currentfont def -X cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto -X fnum show rmoveto currentfont cf setfont(\244)show setfont fden show -X grestore ditwid 0 rmoveto} def -X/oce {grestore ditwid 0 rmoveto}def -X/dm {ditsiz mul}def -X/ocprocs 50 dict def ocprocs begin -X(14){(1)(4)fraction}def -X(12){(1)(2)fraction}def -X(34){(3)(4)fraction}def -X(13){(1)(3)fraction}def -X(23){(2)(3)fraction}def -X(18){(1)(8)fraction}def -X(38){(3)(8)fraction}def -X(58){(5)(8)fraction}def -X(78){(7)(8)fraction}def -X(sr){gsave 0 .06 dm rmoveto(\326)show oce}def -X(is){gsave 0 .15 dm rmoveto(\362)show oce}def -X(->){gsave 0 .02 dm rmoveto(\256)show oce}def -X(<-){gsave 0 .02 dm rmoveto(\254)show oce}def -X(==){gsave 0 .05 dm rmoveto(\272)show oce}def -Xend -X -X% an attempt at a PostScript FONT to implement ditroff special chars -X% this will enable us to -X% cache the little buggers -X% generate faster, more compact PS out of psdit -X% confuse everyone (including myself)! -X50 dict dup begin -X/FontType 3 def -X/FontName /DIThacks def -X/FontMatrix [.001 0 0 .001 0 0] def -X/FontBBox [-260 -260 900 900] def% a lie but ... -X/Encoding 256 array def -X0 1 255{Encoding exch /.notdef put}for -XEncoding -X dup 8#040/space put %space -X dup 8#110/rc put %right ceil -X dup 8#111/lt put %left top curl -X dup 8#112/bv put %bold vert -X dup 8#113/lk put %left mid curl -X dup 8#114/lb put %left bot curl -X dup 8#115/rt put %right top curl -X dup 8#116/rk put %right mid curl -X dup 8#117/rb put %right bot curl -X dup 8#120/rf put %right floor -X dup 8#121/lf put %left floor -X dup 8#122/lc put %left ceil -X dup 8#140/sq put %square -X dup 8#141/bx put %box -X dup 8#142/ci put %circle -X dup 8#143/br put %box rule -X dup 8#144/rn put %root extender -X dup 8#145/vr put %vertical rule -X dup 8#146/ob put %outline bullet -X dup 8#147/bu put %bullet -X dup 8#150/ru put %rule -X dup 8#151/ul put %underline -X pop -X/DITfd 100 dict def -X/BuildChar{0 begin -X /cc exch def /fd exch def -X /charname fd /Encoding get cc get def -X /charwid fd /Metrics get charname get def -X /charproc fd /CharProcs get charname get def -X charwid 0 fd /FontBBox get aload pop setcachedevice -X 2 setlinejoin 40 setlinewidth -X newpath 0 0 moveto gsave charproc grestore -X end}def -X/BuildChar load 0 DITfd put -X%/UniqueID 5 def -X/CharProcs 50 dict def -XCharProcs begin -X/space{}def -X/.notdef{}def -X/ru{500 0 rls}def -X/rn{0 840 moveto 500 0 rls}def -X/vr{0 800 moveto 0 -770 rls}def -X/bv{0 800 moveto 0 -1000 rls}def -X/br{0 750 moveto 0 -1000 rls}def -X/ul{0 -140 moveto 500 0 rls}def -X/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def -X/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def -X/sq{80 0 rmoveto currentpoint dround newpath moveto -X 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def -X/bx{80 0 rmoveto currentpoint dround newpath moveto -X 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def -X/ci{500 360 rmoveto currentpoint newpath 333 0 360 arc -X 50 setlinewidth stroke}def -X -X/lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def -X/lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def -X/rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def -X/rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def -X/lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub -X 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def -X/rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub -X 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def -X/lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def -X/rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def -X/lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def -X/rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def -Xend -X -X/Metrics 50 dict def Metrics begin -X/.notdef 0 def -X/space 500 def -X/ru 500 def -X/br 0 def -X/lt 416 def -X/lb 416 def -X/rt 416 def -X/rb 416 def -X/lk 416 def -X/rk 416 def -X/rc 416 def -X/lc 416 def -X/rf 416 def -X/lf 416 def -X/bv 416 def -X/ob 350 def -X/bu 350 def -X/ci 750 def -X/bx 750 def -X/sq 750 def -X/rn 500 def -X/ul 500 def -X/vr 0 def -Xend -X -XDITfd begin -X/s2 500 def /s4 250 def /s3 333 def -X/a4p{arcto pop pop pop pop}def -X/2cx{2 copy exch}def -X/rls{rlineto stroke}def -X/currx{currentpoint pop}def -X/dround{transform round exch round exch itransform} def -Xend -Xend -X/DIThacks exch definefont pop -Xditstart -X(psc)xT -X576 1 1 xr -X1(Times-Roman)xf 1 f -X2(Times-Italic)xf 2 f -X3(Times-Bold)xf 3 f -X4(Times-BoldItalic)xf 4 f -X5(Helvetica)xf 5 f -X6(Helvetica-Bold)xf 6 f -X7(Courier)xf 7 f -X8(Courier-Bold)xf 8 f -X9(Symbol)xf 9 f -X10(DIThacks)xf 10 f -X10 s -X1 f -Xxi -X%%EndProlog -X -X%%Page: 1 1 -X10 s 0 xH 0 xS 1 f -X8 s -X2 f -X12 s -X1778 672(sdbm)N -X3 f -X2004(\320)X -X2124(Substitute)X -X2563(DBM)X -X2237 768(or)N -X1331 864(Berkeley)N -X2 f -X1719(ndbm)X -X3 f -X1956(for)X -X2103(Every)X -X2373(UN*X)X -X1 f -X10 s -X2628 832(1)N -X3 f -X12 s -X2692 864(Made)N -X2951(Simple)X -X2 f -X10 s -X2041 1056(Ozan)N -X2230(\(oz\))X -X2375(Yigit)X -X1 f -X1658 1200(The)N -X1803(Guild)X -X2005(of)X -X2092(PD)X -X2214(Software)X -X2524(Toolmakers)X -X2000 1296(Toronto)N -X2278(-)X -X2325(Canada)X -X1965 1488(oz@nexus.yorku.ca)N -X2 f -X555 1804(Implementation)N -X1078(is)X -X1151(the)X -X1269(sincerest)X -X1574(form)X -X1745(of)X -X1827(\257attery.)X -X2094(\320)X -X2185(L.)X -X2269(Peter)X -X2463(Deutsch)X -X3 f -X555 1996(A)N -X633(The)X -X786(Clone)X -X1006(of)X -X1093(the)X -X2 f -X1220(ndbm)X -X3 f -X1418(library)X -X1 f -X755 2120(The)N -X903(sources)X -X1167(accompanying)X -X1658(this)X -X1796(notice)X -X2015(\320)X -X2 f -X2118(sdbm)X -X1 f -X2309(\320)X -X2411(constitute)X -X2744(the)X -X2864(\256rst)X -X3010(public)X -X3232(release)X -X3478(\(Dec.)X -X3677(1990\))X -X3886(of)X -X3975(a)X -X555 2216(complete)N -X874(clone)X -X1073(of)X -X1165(the)X -X1288(Berkeley)X -X1603(UN*X)X -X2 f -X1842(ndbm)X -X1 f -X2045(library.)X -X2304(The)X -X2 f -X2454(sdbm)X -X1 f -X2648(library)X -X2887(is)X -X2965(meant)X -X3186(to)X -X3273(clone)X -X3472(the)X -X3594(proven)X -X3841(func-)X -X555 2312(tionality)N -X846(of)X -X2 f -X938(ndbm)X -X1 f -X1141(as)X -X1233(closely)X -X1485(as)X -X1576(possible,)X -X1882(including)X -X2208(a)X -X2268(few)X -X2413(improvements.)X -X2915(It)X -X2988(is)X -X3065(practical,)X -X3386(easy)X -X3553(to)X -X3639(understand,)X -X555 2408(and)N -X691(compatible.)X -X1107(The)X -X2 f -X1252(sdbm)X -X1 f -X1441(library)X -X1675(is)X -X1748(not)X -X1870(derived)X -X2131(from)X -X2307(any)X -X2443(licensed,)X -X2746(proprietary)X -X3123(or)X -X3210(copyrighted)X -X3613(software.)X -X755 2532(The)N -X2 f -X910(sdbm)X -X1 f -X1109(implementation)X -X1641(is)X -X1723(based)X -X1935(on)X -X2044(a)X -X2109(1978)X -X2298(algorithm)X -X2638([Lar78])X -X2913(by)X -X3022(P.-A.)X -X3220(\(Paul\))X -X3445(Larson)X -X3697(known)X -X3944(as)X -X555 2628(``Dynamic)N -X934(Hashing''.)X -X1326(In)X -X1424(the)X -X1553(course)X -X1794(of)X -X1892(searching)X -X2231(for)X -X2355(a)X -X2421(substitute)X -X2757(for)X -X2 f -X2881(ndbm)X -X1 f -X3059(,)X -X3109(I)X -X3166(prototyped)X -X3543(three)X -X3734(different)X -X555 2724(external-hashing)N -X1119(algorithms)X -X1490([Lar78,)X -X1758(Fag79,)X -X2007(Lit80])X -X2236(and)X -X2381(ultimately)X -X2734(chose)X -X2946(Larson's)X -X3256(algorithm)X -X3596(as)X -X3692(a)X -X3756(basis)X -X3944(of)X -X555 2820(the)N -X2 f -X680(sdbm)X -X1 f -X875(implementation.)X -X1423(The)X -X1574(Bell)X -X1733(Labs)X -X2 f -X1915(dbm)X -X1 f -X2079(\(and)X -X2248(therefore)X -X2 f -X2565(ndbm)X -X1 f -X2743(\))X -X2796(is)X -X2875(based)X -X3084(on)X -X3190(an)X -X3292(algorithm)X -X3629(invented)X -X3931(by)X -X555 2916(Ken)N -X709(Thompson,)X -X1091([Tho90,)X -X1367(Tor87])X -X1610(and)X -X1746(predates)X -X2034(Larson's)X -X2335(work.)X -X755 3040(The)N -X2 f -X903(sdbm)X -X1 f -X1095(programming)X -X1553(interface)X -X1857(is)X -X1932(totally)X -X2158(compatible)X -X2536(with)X -X2 f -X2700(ndbm)X -X1 f -X2900(and)X -X3038(includes)X -X3327(a)X -X3385(slight)X -X3584(improvement)X -X555 3136(in)N -X641(database)X -X942(initialization.)X -X1410(It)X -X1483(is)X -X1560(also)X -X1713(expected)X -X2023(to)X -X2109(be)X -X2208(binary-compatible)X -X2819(under)X -X3025(most)X -X3203(UN*X)X -X3440(versions)X -X3730(that)X -X3873(sup-)X -X555 3232(port)N -X704(the)X -X2 f -X822(ndbm)X -X1 f -X1020(library.)X -X755 3356(The)N -X2 f -X909(sdbm)X -X1 f -X1107(implementation)X -X1638(shares)X -X1868(the)X -X1995(shortcomings)X -X2455(of)X -X2551(the)X -X2 f -X2678(ndbm)X -X1 f -X2885(library,)X -X3148(as)X -X3244(a)X -X3309(side)X -X3467(effect)X -X3680(of)X -X3775(various)X -X555 3452(simpli\256cations)N -X1046(to)X -X1129(the)X -X1248(original)X -X1518(Larson)X -X1762(algorithm.)X -X2114(It)X -X2183(does)X -X2350(produce)X -X2 f -X2629(holes)X -X1 f -X2818(in)X -X2900(the)X -X3018(page)X -X3190(\256le)X -X3312(as)X -X3399(it)X -X3463(writes)X -X3679(pages)X -X3882(past)X -X555 3548(the)N -X680(end)X -X823(of)X -X917(\256le.)X -X1066(\(Larson's)X -X1400(paper)X -X1605(include)X -X1867(a)X -X1929(clever)X -X2152(solution)X -X2435(to)X -X2523(this)X -X2664(problem)X -X2957(that)X -X3103(is)X -X3182(a)X -X3244(result)X -X3448(of)X -X3541(using)X -X3740(the)X -X3864(hash)X -X555 3644(value)N -X758(directly)X -X1032(as)X -X1128(a)X -X1193(block)X -X1400(address.\))X -X1717(On)X -X1844(the)X -X1971(other)X -X2165(hand,)X -X2370(extensive)X -X2702(tests)X -X2873(seem)X -X3067(to)X -X3158(indicate)X -X3441(that)X -X2 f -X3590(sdbm)X -X1 f -X3787(creates)X -X555 3740(fewer)N -X762(holes)X -X954(in)X -X1039(general,)X -X1318(and)X -X1456(the)X -X1576(resulting)X -X1878(page\256les)X -X2185(are)X -X2306(smaller.)X -X2584(The)X -X2 f -X2731(sdbm)X -X1 f -X2922(implementation)X -X3446(is)X -X3521(also)X -X3672(faster)X -X3873(than)X -X2 f -X555 3836(ndbm)N -X1 f -X757(in)X -X843(database)X -X1144(creation.)X -X1467(Unlike)X -X1709(the)X -X2 f -X1831(ndbm)X -X1 f -X2009(,)X -X2053(the)X -X2 f -X2175(sdbm)X -X7 f -X2396(store)X -X1 f -X2660(operation)X -X2987(will)X -X3134(not)X -X3259(``wander)X -X3573(away'')X -X3820(trying)X -X555 3932(to)N -X642(split)X -X804(its)X -X904(data)X -X1063(pages)X -X1271(to)X -X1358(insert)X -X1561(a)X -X1622(datum)X -X1847(that)X -X2 f -X1992(cannot)X -X1 f -X2235(\(due)X -X2403(to)X -X2490(elaborate)X -X2810(worst-case)X -X3179(situations\))X -X3537(be)X -X3637(inserted.)X -X3935(\(It)X -X555 4028(will)N -X699(fail)X -X826(after)X -X994(a)X -X1050(pre-de\256ned)X -X1436(number)X -X1701(of)X -X1788(attempts.\))X -X3 f -X555 4220(Important)N -X931(Compatibility)X -X1426(Warning)X -X1 f -X755 4344(The)N -X2 f -X904(sdbm)X -X1 f -X1097(and)X -X2 f -X1237(ndbm)X -X1 f -X1439(libraries)X -X2 f -X1726(cannot)X -X1 f -X1968(share)X -X2162(databases:)X -X2515(one)X -X2654(cannot)X -X2891(read)X -X3053(the)X -X3174(\(dir/pag\))X -X3478(database)X -X3778(created)X -X555 4440(by)N -X657(the)X -X777(other.)X -X984(This)X -X1148(is)X -X1222(due)X -X1359(to)X -X1442(the)X -X1561(differences)X -X1940(between)X -X2229(the)X -X2 f -X2348(ndbm)X -X1 f -X2547(and)X -X2 f -X2684(sdbm)X -X1 f -X2874(algorithms)X -X8 s -X3216 4415(2)N -X10 s -X4440(,)Y -X3289(and)X -X3426(the)X -X3545(hash)X -X3713(functions)X -X555 4536(used.)N -X769(It)X -X845(is)X -X925(easy)X -X1094(to)X -X1182(convert)X -X1449(between)X -X1743(the)X -X2 f -X1867(dbm/ndbm)X -X1 f -X2231(databases)X -X2565(and)X -X2 f -X2707(sdbm)X -X1 f -X2902(by)X -X3008(ignoring)X -X3305(the)X -X3429(index)X -X3633(completely:)X -X555 4632(see)N -X7 f -X706(dbd)X -X1 f -X(,)S -X7 f -X918(dbu)X -X1 f -X1082(etc.)X -X3 f -X555 4852(Notice)N -X794(of)X -X881(Intellectual)X -X1288(Property)X -X2 f -X555 4976(The)N -X696(entire)X -X1 f -X904(sdbm)X -X2 f -X1118(library)X -X1361(package,)X -X1670(as)X -X1762(authored)X -X2072(by)X -X2169(me,)X -X1 f -X2304(Ozan)X -X2495(S.)X -X2580(Yigit,)X -X2 f -X2785(is)X -X2858(hereby)X -X3097(placed)X -X3331(in)X -X3413(the)X -X3531(public)X -X3751(domain.)X -X1 f -X555 5072(As)N -X670(such,)X -X863(the)X -X987(author)X -X1218(is)X -X1297(not)X -X1425(responsible)X -X1816(for)X -X1936(the)X -X2060(consequences)X -X2528(of)X -X2621(use)X -X2754(of)X -X2847(this)X -X2988(software,)X -X3310(no)X -X3415(matter)X -X3645(how)X -X3808(awful,)X -X555 5168(even)N -X727(if)X -X796(they)X -X954(arise)X -X1126(from)X -X1302(defects)X -X1550(in)X -X1632(it.)X -X1716(There)X -X1924(is)X -X1997(no)X -X2097(expressed)X -X2434(or)X -X2521(implied)X -X2785(warranty)X -X3091(for)X -X3205(the)X -X2 f -X3323(sdbm)X -X1 f -X3512(library.)X -X8 s -X10 f -X555 5316(hhhhhhhhhhhhhhhhhh)N -X6 s -X1 f -X635 5391(1)N -X8 s -X691 5410(UN*X)N -X877(is)X -X936(not)X -X1034(a)X -X1078(trademark)X -X1352(of)X -X1421(any)X -X1529(\(dis\)organization.)X -X6 s -X635 5485(2)N -X8 s -X691 5504(Torek's)N -X908(discussion)X -X1194([Tor87])X -X1411(indicates)X -X1657(that)X -X2 f -X1772(dbm/ndbm)X -X1 f -X2061(implementations)X -X2506(use)X -X2609(the)X -X2705(hash)X -X2840(value)X -X2996(to)X -X3064(traverse)X -X3283(the)X -X3379(radix)X -X3528(trie)X -X3631(dif-)X -X555 5584(ferently)N -X772(than)X -X2 f -X901(sdbm)X -X1 f -X1055(and)X -X1166(as)X -X1238(a)X -X1285(result,)X -X1462(the)X -X1559(page)X -X1698(indexes)X -X1912(are)X -X2008(generated)X -X2274(in)X -X2 f -X2343(different)X -X1 f -X2579(order.)X -X2764(For)X -X2872(more)X -X3021(information,)X -X3357(send)X -X3492(e-mail)X -X3673(to)X -X555 5664(the)N -X649(author.)X -X -X2 p -X%%Page: 2 2 -X8 s 0 xH 0 xS 1 f -X10 s -X2216 384(-)N -X2263(2)X -X2323(-)X -X755 672(Since)N -X971(the)X -X2 f -X1107(sdbm)X -X1 f -X1314(library)X -X1566(package)X -X1868(is)X -X1959(in)X -X2058(the)X -X2193(public)X -X2430(domain,)X -X2727(this)X -X2 f -X2879(original)X -X1 f -X3173(release)X -X3434(or)X -X3538(any)X -X3691(additional)X -X555 768(public-domain)N -X1045(releases)X -X1323(of)X -X1413(the)X -X1534(modi\256ed)X -X1841(original)X -X2112(cannot)X -X2348(possibly)X -X2636(\(by)X -X2765(de\256nition\))X -X3120(be)X -X3218(withheld)X -X3520(from)X -X3698(you.)X -X3860(Also)X -X555 864(by)N -X659(de\256nition,)X -X1009(You)X -X1170(\(singular\))X -X1505(have)X -X1680(all)X -X1783(the)X -X1904(rights)X -X2109(to)X -X2194(this)X -X2332(code)X -X2507(\(including)X -X2859(the)X -X2980(right)X -X3154(to)X -X3239(sell)X -X3373(without)X -X3640(permission,)X -X555 960(the)N -X679(right)X -X856(to)X -X944(hoard)X -X8 s -X1127 935(3)N -X10 s -X1185 960(and)N -X1327(the)X -X1451(right)X -X1628(to)X -X1716(do)X -X1821(other)X -X2011(icky)X -X2174(things)X -X2394(as)X -X2486(you)X -X2631(see)X -X2759(\256t\))X -X2877(but)X -X3004(those)X -X3198(rights)X -X3405(are)X -X3529(also)X -X3683(granted)X -X3949(to)X -X555 1056(everyone)N -X870(else.)X -X755 1180(Please)N -X997(note)X -X1172(that)X -X1329(all)X -X1446(previous)X -X1759(distributions)X -X2195(of)X -X2298(this)X -X2449(software)X -X2762(contained)X -X3110(a)X -X3182(copyright)X -X3525(\(which)X -X3784(is)X -X3873(now)X -X555 1276(dropped\))N -X868(to)X -X953(protect)X -X1199(its)X -X1297(origins)X -X1542(and)X -X1681(its)X -X1779(current)X -X2030(public)X -X2253(domain)X -X2516(status)X -X2721(against)X -X2970(any)X -X3108(possible)X -X3392(claims)X -X3623(and/or)X -X3850(chal-)X -X555 1372(lenges.)N -X3 f -X555 1564(Acknowledgments)N -X1 f -X755 1688(Many)N -X966(people)X -X1204(have)X -X1380(been)X -X1556(very)X -X1723(helpful)X -X1974(and)X -X2114(supportive.)X -X2515(A)X -X2596(partial)X -X2824(list)X -X2944(would)X -X3167(necessarily)X -X3547(include)X -X3806(Rayan)X -X555 1784(Zacherissen)N -X963(\(who)X -X1152(contributed)X -X1541(the)X -X1663(man)X -X1824(page,)X -X2019(and)X -X2158(also)X -X2310(hacked)X -X2561(a)X -X2620(MMAP)X -X2887(version)X -X3146(of)X -X2 f -X3236(sdbm)X -X1 f -X3405(\),)X -X3475(Arnold)X -X3725(Robbins,)X -X555 1880(Chris)N -X763(Lewis,)X -X1013(Bill)X -X1166(Davidsen,)X -X1523(Henry)X -X1758(Spencer,)X -X2071(Geoff)X -X2293(Collyer,)X -X2587(Rich)X -X2772(Salz)X -X2944(\(who)X -X3143(got)X -X3279(me)X -X3411(started)X -X3659(in)X -X3755(the)X -X3887(\256rst)X -X555 1976(place\),)N -X792(Johannes)X -X1106(Ruschein)X -X1424(\(who)X -X1609(did)X -X1731(the)X -X1849(minix)X -X2055(port\))X -X2231(and)X -X2367(David)X -X2583(Tilbrook.)X -X2903(I)X -X2950(thank)X -X3148(you)X -X3288(all.)X -X3 f -X555 2168(Distribution)N -X992(Manifest)X -X1315(and)X -X1463(Notes)X -X1 f -X555 2292(This)N -X717(distribution)X -X1105(of)X -X2 f -X1192(sdbm)X -X1 f -X1381(includes)X -X1668(\(at)X -X1773(least\))X -X1967(the)X -X2085(following:)X -X7 f -X747 2436(CHANGES)N -X1323(change)X -X1659(log)X -X747 2532(README)N -X1323(this)X -X1563(file.)X -X747 2628(biblio)N -X1323(a)X -X1419(small)X -X1707(bibliography)X -X2331(on)X -X2475(external)X -X2907(hashing)X -X747 2724(dba.c)N -X1323(a)X -X1419(crude)X -X1707(\(n/s\)dbm)X -X2139(page)X -X2379(file)X -X2619(analyzer)X -X747 2820(dbd.c)N -X1323(a)X -X1419(crude)X -X1707(\(n/s\)dbm)X -X2139(page)X -X2379(file)X -X2619(dumper)X -X2955(\(for)X -X3195(conversion\))X -X747 2916(dbe.1)N -X1323(man)X -X1515(page)X -X1755(for)X -X1947(dbe.c)X -X747 3012(dbe.c)N -X1323(Janick's)X -X1755(database)X -X2187(editor)X -X747 3108(dbm.c)N -X1323(a)X -X1419(dbm)X -X1611(library)X -X1995(emulation)X -X2475(wrapper)X -X2859(for)X -X3051(ndbm/sdbm)X -X747 3204(dbm.h)N -X1323(header)X -X1659(file)X -X1899(for)X -X2091(the)X -X2283(above)X -X747 3300(dbu.c)N -X1323(a)X -X1419(crude)X -X1707(db)X -X1851(management)X -X2379(utility)X -X747 3396(hash.c)N -X1323(hashing)X -X1707(function)X -X747 3492(makefile)N -X1323(guess.)X -X747 3588(pair.c)N -X1323(page-level)X -X1851(routines)X -X2283(\(posted)X -X2667(earlier\))X -X747 3684(pair.h)N -X1323(header)X -X1659(file)X -X1899(for)X -X2091(the)X -X2283(above)X -X747 3780(readme.ms)N -X1323(troff)X -X1611(source)X -X1947(for)X -X2139(the)X -X2331(README)X -X2667(file)X -X747 3876(sdbm.3)N -X1323(man)X -X1515(page)X -X747 3972(sdbm.c)N -X1323(the)X -X1515(real)X -X1755(thing)X -X747 4068(sdbm.h)N -X1323(header)X -X1659(file)X -X1899(for)X -X2091(the)X -X2283(above)X -X747 4164(tune.h)N -X1323(place)X -X1611(for)X -X1803(tuning)X -X2139(&)X -X2235(portability)X -X2811(thingies)X -X747 4260(util.c)N -X1323(miscellaneous)X -X755 4432(dbu)N -X1 f -X924(is)X -X1002(a)X -X1063(simple)X -X1301(database)X -X1603(manipulation)X -X2050(program)X -X8 s -X2322 4407(4)N -X10 s -X2379 4432(that)N -X2524(tries)X -X2687(to)X -X2774(look)X -X2941(like)X -X3086(Bell)X -X3244(Labs')X -X7 f -X3480(cbt)X -X1 f -X3649(utility.)X -X3884(It)X -X3958(is)X -X555 4528(currently)N -X867(incomplete)X -X1245(in)X -X1329(functionality.)X -X1800(I)X -X1849(use)X -X7 f -X2006(dbu)X -X1 f -X2172(to)X -X2255(test)X -X2387(out)X -X2510(the)X -X2629(routines:)X -X2930(it)X -X2995(takes)X -X3181(\(from)X -X3385(stdin\))X -X3588(tab)X -X3707(separated)X -X555 4624(key/value)N -X898(pairs)X -X1085(for)X -X1210(commands)X -X1587(like)X -X7 f -X1765(build)X -X1 f -X2035(or)X -X7 f -X2160(insert)X -X1 f -X2478(or)X -X2575(takes)X -X2770(keys)X -X2947(for)X -X3071(commands)X -X3448(like)X -X7 f -X3626(delete)X -X1 f -X3944(or)X -X7 f -X555 4720(look)N -X1 f -X(.)S -X7 f -X747 4864(dbu)N -X939(<build|creat|look|insert|cat|delete>)X -X2715(dbmfile)X -X755 5036(dba)N -X1 f -X927(is)X -X1008(a)X -X1072(crude)X -X1279(analyzer)X -X1580(of)X -X2 f -X1675(dbm/sdbm/ndbm)X -X1 f -X2232(page)X -X2412(\256les.)X -X2593(It)X -X2670(scans)X -X2872(the)X -X2998(entire)X -X3209(page)X -X3389(\256le,)X -X3538(reporting)X -X3859(page)X -X555 5132(level)N -X731(statistics,)X -X1046(and)X -X1182(totals)X -X1375(at)X -X1453(the)X -X1571(end.)X -X7 f -X755 5256(dbd)N -X1 f -X925(is)X -X1004(a)X -X1066(crude)X -X1271(dump)X -X1479(program)X -X1777(for)X -X2 f -X1897(dbm/ndbm/sdbm)X -X1 f -X2452(databases.)X -X2806(It)X -X2881(ignores)X -X3143(the)X -X3267(bitmap,)X -X3534(and)X -X3675(dumps)X -X3913(the)X -X555 5352(data)N -X717(pages)X -X928(in)X -X1018(sequence.)X -X1361(It)X -X1437(can)X -X1576(be)X -X1679(used)X -X1853(to)X -X1942(create)X -X2162(input)X -X2353(for)X -X2474(the)X -X7 f -X2627(dbu)X -X1 f -X2798(utility.)X -X3055(Note)X -X3238(that)X -X7 f -X3413(dbd)X -X1 f -X3584(will)X -X3735(skip)X -X3895(any)X -X8 s -X10 f -X555 5432(hhhhhhhhhhhhhhhhhh)N -X6 s -X1 f -X635 5507(3)N -X8 s -X691 5526(You)N -X817(cannot)X -X1003(really)X -X1164(hoard)X -X1325(something)X -X1608(that)X -X1720(is)X -X1779(available)X -X2025(to)X -X2091(the)X -X2185(public)X -X2361(at)X -X2423(large,)X -X2582(but)X -X2680(try)X -X2767(if)X -X2822(it)X -X2874(makes)X -X3053(you)X -X3165(feel)X -X3276(any)X -X3384(better.)X -X6 s -X635 5601(4)N -X8 s -X691 5620(The)N -X7 f -X829(dbd)X -X1 f -X943(,)X -X7 f -X998(dba)X -X1 f -X1112(,)X -X7 f -X1167(dbu)X -X1 f -X1298(utilities)X -X1508(are)X -X1602(quick)X -X1761(hacks)X -X1923(and)X -X2032(are)X -X2126(not)X -X2225(\256t)X -X2295(for)X -X2385(production)X -X2678(use.)X -X2795(They)X -X2942(were)X -X3081(developed)X -X3359(late)X -X3467(one)X -X3575(night,)X -X555 5700(just)N -X664(to)X -X730(test)X -X835(out)X -X2 f -X933(sdbm)X -X1 f -X1068(,)X -X1100(and)X -X1208(convert)X -X1415(some)X -X1566(databases.)X -X -X3 p -X%%Page: 3 3 -X8 s 0 xH 0 xS 1 f -X10 s -X2216 384(-)N -X2263(3)X -X2323(-)X -X555 672(NULLs)N -X821(in)X -X903(the)X -X1021(key)X -X1157(and)X -X1293(data)X -X1447(\256elds,)X -X1660(thus)X -X1813(is)X -X1886(unsuitable)X -X2235(to)X -X2317(convert)X -X2578(some)X -X2767(peculiar)X -X3046(databases)X -X3374(that)X -X3514(insist)X -X3702(in)X -X3784(includ-)X -X555 768(ing)N -X677(the)X -X795(terminating)X -X1184(null.)X -X755 892(I)N -X841(have)X -X1052(also)X -X1240(included)X -X1575(a)X -X1670(copy)X -X1885(of)X -X2011(the)X -X7 f -X2195(dbe)X -X1 f -X2397(\()X -X2 f -X2424(ndbm)X -X1 f -X2660(DataBase)X -X3026(Editor\))X -X3311(by)X -X3449(Janick)X -X3712(Bergeron)X -X555 988([janick@bnr.ca])N -X1098(for)X -X1212(your)X -X1379(pleasure.)X -X1687(You)X -X1845(may)X -X2003(\256nd)X -X2147(it)X -X2211(more)X -X2396(useful)X -X2612(than)X -X2770(the)X -X2888(little)X -X7 f -X3082(dbu)X -X1 f -X3246(utility.)X -X7 f -X755 1112(dbm.[ch])N -X1 f -X1169(is)X -X1252(a)X -X2 f -X1318(dbm)X -X1 f -X1486(library)X -X1730(emulation)X -X2079(on)X -X2188(top)X -X2319(of)X -X2 f -X2415(ndbm)X -X1 f -X2622(\(and)X -X2794(hence)X -X3011(suitable)X -X3289(for)X -X2 f -X3412(sdbm)X -X1 f -X3581(\).)X -X3657(Written)X -X3931(by)X -X555 1208(Robert)N -X793(Elz.)X -X755 1332(The)N -X2 f -X901(sdbm)X -X1 f -X1090(library)X -X1324(has)X -X1451(been)X -X1623(around)X -X1866(in)X -X1948(beta)X -X2102(test)X -X2233(for)X -X2347(quite)X -X2527(a)X -X2583(long)X -X2745(time,)X -X2927(and)X -X3063(from)X -X3239(whatever)X -X3554(little)X -X3720(feedback)X -X555 1428(I)N -X609(received)X -X909(\(maybe)X -X1177(no)X -X1284(news)X -X1476(is)X -X1555(good)X -X1741(news\),)X -X1979(I)X -X2032(believe)X -X2290(it)X -X2360(has)X -X2493(been)X -X2671(functioning)X -X3066(without)X -X3336(any)X -X3478(signi\256cant)X -X3837(prob-)X -X555 1524(lems.)N -X752(I)X -X805(would,)X -X1051(of)X -X1144(course,)X -X1400(appreciate)X -X1757(all)X -X1863(\256xes)X -X2040(and/or)X -X2271(improvements.)X -X2774(Portability)X -X3136(enhancements)X -X3616(would)X -X3841(espe-)X -X555 1620(cially)N -X753(be)X -X849(useful.)X -X3 f -X555 1812(Implementation)N -X1122(Issues)X -X1 f -X755 1936(Hash)N -X944(functions:)X -X1288(The)X -X1437(algorithm)X -X1772(behind)X -X2 f -X2014(sdbm)X -X1 f -X2207(implementation)X -X2733(needs)X -X2939(a)X -X2998(good)X -X3181(bit-scrambling)X -X3671(hash)X -X3841(func-)X -X555 2032(tion)N -X702(to)X -X787(be)X -X886(effective.)X -X1211(I)X -X1261(ran)X -X1387(into)X -X1534(a)X -X1593(set)X -X1705(of)X -X1795(constants)X -X2116(for)X -X2233(a)X -X2292(simple)X -X2528(hash)X -X2698(function)X -X2988(that)X -X3130(seem)X -X3317(to)X -X3401(help)X -X2 f -X3561(sdbm)X -X1 f -X3752(perform)X -X555 2128(better)N -X758(than)X -X2 f -X916(ndbm)X -X1 f -X1114(for)X -X1228(various)X -X1484(inputs:)X -X7 f -X747 2272(/*)N -X795 2368(*)N -X891(polynomial)X -X1419(conversion)X -X1947(ignoring)X -X2379(overflows)X -X795 2464(*)N -X891(65599)X -X1179(nice.)X -X1467(65587)X -X1755(even)X -X1995(better.)X -X795 2560(*/)N -X747 2656(long)N -X747 2752(dbm_hash\(char)N -X1419(*str,)X -X1707(int)X -X1899(len\))X -X2139({)X -X939 2848(register)N -X1371(unsigned)X -X1803(long)X -X2043(n)X -X2139(=)X -X2235(0;)X -X939 3040(while)N -X1227(\(len--\))X -X1131 3136(n)N -X1227(=)X -X1323(n)X -X1419(*)X -X1515(65599)X -X1803(+)X -X1899(*str++;)X -X939 3232(return)N -X1275(n;)X -X747 3328(})N -X1 f -X755 3500(There)N -X975(may)X -X1145(be)X -X1253(better)X -X1467(hash)X -X1645(functions)X -X1974(for)X -X2099(the)X -X2228(purposes)X -X2544(of)X -X2642(dynamic)X -X2949(hashing.)X -X3269(Try)X -X3416(your)X -X3594(favorite,)X -X3895(and)X -X555 3596(check)N -X766(the)X -X887(page\256le.)X -X1184(If)X -X1261(it)X -X1328(contains)X -X1618(too)X -X1743(many)X -X1944(pages)X -X2150(with)X -X2315(too)X -X2440(many)X -X2641(holes,)X -X2853(\(in)X -X2965(relation)X -X3233(to)X -X3318(this)X -X3456(one)X -X3595(for)X -X3712(example\))X -X555 3692(or)N -X656(if)X -X2 f -X739(sdbm)X -X1 f -X942(simply)X -X1193(stops)X -X1391(working)X -X1692(\(fails)X -X1891(after)X -X7 f -X2101(SPLTMAX)X -X1 f -X2471(attempts)X -X2776(to)X -X2872(split\))X -X3070(when)X -X3278(you)X -X3432(feed)X -X3604(your)X -X3784(NEWS)X -X7 f -X555 3788(history)N -X1 f -X912(\256le)X -X1035(to)X -X1118(it,)X -X1203(you)X -X1344(probably)X -X1650(do)X -X1751(not)X -X1874(have)X -X2047(a)X -X2104(good)X -X2285(hashing)X -X2555(function.)X -X2883(If)X -X2958(you)X -X3099(do)X -X3200(better)X -X3404(\(for)X -X3545(different)X -X3842(types)X -X555 3884(of)N -X642(input\),)X -X873(I)X -X920(would)X -X1140(like)X -X1280(to)X -X1362(know)X -X1560(about)X -X1758(the)X -X1876(function)X -X2163(you)X -X2303(use.)X -X755 4008(Block)N -X967(sizes:)X -X1166(It)X -X1236(seems)X -X1453(\(from)X -X1657(various)X -X1914(tests)X -X2077(on)X -X2178(a)X -X2235(few)X -X2377(machines\))X -X2727(that)X -X2867(a)X -X2923(page)X -X3095(\256le)X -X3217(block)X -X3415(size)X -X7 f -X3588(PBLKSIZ)X -X1 f -X3944(of)X -X555 4104(1024)N -X738(is)X -X814(by)X -X917(far)X -X1030(the)X -X1150(best)X -X1301(for)X -X1417(performance,)X -X1866(but)X -X1990(this)X -X2127(also)X -X2278(happens)X -X2563(to)X -X2647(limit)X -X2819(the)X -X2939(size)X -X3086(of)X -X3175(a)X -X3233(key/value)X -X3567(pair.)X -X3734(Depend-)X -X555 4200(ing)N -X681(on)X -X785(your)X -X956(needs,)X -X1183(you)X -X1327(may)X -X1489(wish)X -X1663(to)X -X1748(increase)X -X2035(the)X -X2156(page)X -X2331(size,)X -X2499(and)X -X2638(also)X -X2790(adjust)X -X7 f -X3032(PAIRMAX)X -X1 f -X3391(\(the)X -X3539(maximum)X -X3886(size)X -X555 4296(of)N -X648(a)X -X710(key/value)X -X1048(pair)X -X1199(allowed:)X -X1501(should)X -X1740(always)X -X1989(be)X -X2090(at)X -X2173(least)X -X2345(three)X -X2531(words)X -X2752(smaller)X -X3013(than)X -X7 f -X3204(PBLKSIZ)X -X1 f -X(.\))S -X3612(accordingly.)X -X555 4392(The)N -X706(system-wide)X -X1137(version)X -X1399(of)X -X1492(the)X -X1616(library)X -X1856(should)X -X2095(probably)X -X2406(be)X -X2508(con\256gured)X -X2877(with)X -X3044(1024)X -X3229(\(distribution)X -X3649(default\),)X -X3944(as)X -X555 4488(this)N -X690(appears)X -X956(to)X -X1038(be)X -X1134(suf\256cient)X -X1452(for)X -X1566(most)X -X1741(common)X -X2041(uses)X -X2199(of)X -X2 f -X2286(sdbm)X -X1 f -X2455(.)X -X3 f -X555 4680(Portability)N -X1 f -X755 4804(This)N -X917(package)X -X1201(has)X -X1328(been)X -X1500(tested)X -X1707(in)X -X1789(many)X -X1987(different)X -X2284(UN*Xes)X -X2585(even)X -X2757(including)X -X3079(minix,)X -X3305(and)X -X3441(appears)X -X3707(to)X -X3789(be)X -X3885(rea-)X -X555 4900(sonably)N -X824(portable.)X -X1127(This)X -X1289(does)X -X1456(not)X -X1578(mean)X -X1772(it)X -X1836(will)X -X1980(port)X -X2129(easily)X -X2336(to)X -X2418(non-UN*X)X -X2799(systems.)X -X3 f -X555 5092(Notes)N -X767(and)X -X915(Miscellaneous)X -X1 f -X755 5216(The)N -X2 f -X913(sdbm)X -X1 f -X1115(is)X -X1201(not)X -X1336(a)X -X1405(very)X -X1581(complicated)X -X2006(package,)X -X2323(at)X -X2414(least)X -X2594(not)X -X2729(after)X -X2910(you)X -X3063(familiarize)X -X3444(yourself)X -X3739(with)X -X3913(the)X -X555 5312(literature)N -X879(on)X -X993(external)X -X1286(hashing.)X -X1589(There)X -X1811(are)X -X1944(other)X -X2143(interesting)X -X2514(algorithms)X -X2889(in)X -X2984(existence)X -X3316(that)X -X3469(ensure)X -X3712(\(approxi-)X -X555 5408(mately\))N -X825(single-read)X -X1207(access)X -X1438(to)X -X1525(a)X -X1586(data)X -X1745(value)X -X1944(associated)X -X2299(with)X -X2466(any)X -X2607(key.)X -X2768(These)X -X2984(are)X -X3107(directory-less)X -X3568(schemes)X -X3864(such)X -X555 5504(as)N -X2 f -X644(linear)X -X857(hashing)X -X1 f -X1132([Lit80])X -X1381(\(+)X -X1475(Larson)X -X1720(variations\),)X -X2 f -X2105(spiral)X -X2313(storage)X -X1 f -X2575([Mar79])X -X2865(or)X -X2954(directory)X -X3265(schemes)X -X3558(such)X -X3726(as)X -X2 f -X3814(exten-)X -X555 5600(sible)N -X731(hashing)X -X1 f -X1009([Fag79])X -X1288(by)X -X1393(Fagin)X -X1600(et)X -X1683(al.)X -X1786(I)X -X1838(do)X -X1943(hope)X -X2124(these)X -X2314(sources)X -X2579(provide)X -X2848(a)X -X2908(reasonable)X -X3276(playground)X -X3665(for)X -X3783(experi-)X -X555 5696(mentation)N -X907(with)X -X1081(other)X -X1277(algorithms.)X -X1690(See)X -X1837(the)X -X1966(June)X -X2144(1988)X -X2335(issue)X -X2526(of)X -X2624(ACM)X -X2837(Computing)X -X3227(Surveys)X -X3516([Enb88])X -X3810(for)X -X3935(an)X -X555 5792(excellent)N -X865(overview)X -X1184(of)X -X1271(the)X -X1389(\256eld.)X -X -X4 p -X%%Page: 4 4 -X10 s 0 xH 0 xS 1 f -X2216 384(-)N -X2263(4)X -X2323(-)X -X3 f -X555 672(References)N -X1 f -X555 824([Lar78])N -X875(P.-A.)X -X1064(Larson,)X -X1327(``Dynamic)X -X1695(Hashing'',)X -X2 f -X2056(BIT)X -X1 f -X(,)S -X2216(vol.)X -X2378(18,)X -X2518(pp.)X -X2638(184-201,)X -X2945(1978.)X -X555 948([Tho90])N -X875(Ken)X -X1029(Thompson,)X -X2 f -X1411(private)X -X1658(communication)X -X1 f -X2152(,)X -X2192(Nov.)X -X2370(1990)X -X555 1072([Lit80])N -X875(W.)X -X992(Litwin,)X -X1246(``)X -X1321(Linear)X -X1552(Hashing:)X -X1862(A)X -X1941(new)X -X2096(tool)X -X2261(for)X -X2396(\256le)X -X2539(and)X -X2675(table)X -X2851(addressing'',)X -X2 f -X3288(Proceedings)X -X3709(of)X -X3791(the)X -X3909(6th)X -X875 1168(Conference)N -X1269(on)X -X1373(Very)X -X1548(Large)X -X1782(Dabatases)X -X2163(\(Montreal\))X -X1 f -X2515(,)X -X2558(pp.)X -X2701(212-223,)X -X3031(Very)X -X3215(Large)X -X3426(Database)X -X3744(Founda-)X -X875 1264(tion,)N -X1039(Saratoga,)X -X1360(Calif.,)X -X1580(1980.)X -X555 1388([Fag79])N -X875(R.)X -X969(Fagin,)X -X1192(J.)X -X1284(Nievergelt,)X -X1684(N.)X -X1803(Pippinger,)X -X2175(and)X -X2332(H.)X -X2451(R.)X -X2544(Strong,)X -X2797(``Extendible)X -X3218(Hashing)X -X3505(-)X -X3552(A)X -X3630(Fast)X -X3783(Access)X -X875 1484(Method)N -X1144(for)X -X1258(Dynamic)X -X1572(Files'',)X -X2 f -X1821(ACM)X -X2010(Trans.)X -X2236(Database)X -X2563(Syst.)X -X1 f -X2712(,)X -X2752(vol.)X -X2894(4,)X -X2994(no.3,)X -X3174(pp.)X -X3294(315-344,)X -X3601(Sept.)X -X3783(1979.)X -X555 1608([Wal84])N -X875(Rich)X -X1055(Wales,)X -X1305(``Discussion)X -X1739(of)X -X1835("dbm")X -X2072(data)X -X2235(base)X -X2406(system'',)X -X2 f -X2730(USENET)X -X3051(newsgroup)X -X3430(unix.wizards)X -X1 f -X3836(,)X -X3884(Jan.)X -X875 1704(1984.)N -X555 1828([Tor87])N -X875(Chris)X -X1068(Torek,)X -X1300(``Re:)X -X1505(dbm.a)X -X1743(and)X -X1899(ndbm.a)X -X2177(archives'',)X -X2 f -X2539(USENET)X -X2852(newsgroup)X -X3223(comp.unix)X -X1 f -X3555(,)X -X3595(1987.)X -X555 1952([Mar79])N -X875(G.)X -X974(N.)X -X1073(Martin,)X -X1332(``Spiral)X -X1598(Storage:)X -X1885(Incrementally)X -X2371(Augmentable)X -X2843(Hash)X -X3048(Addressed)X -X3427(Storage'',)X -X2 f -X3766(Techni-)X -X875 2048(cal)N -X993(Report)X -X1231(#27)X -X1 f -X(,)S -X1391(University)X -X1749(of)X -X1836(Varwick,)X -X2153(Coventry,)X -X2491(U.K.,)X -X2687(1979.)X -X555 2172([Enb88])N -X875(R.)X -X977(J.)X -X1057(Enbody)X -X1335(and)X -X1480(H.)X -X1586(C.)X -X1687(Du,)X -X1833(``Dynamic)X -X2209(Hashing)X -X2524(Schemes'',)X -X2 f -X2883(ACM)X -X3080(Computing)X -X3463(Surveys)X -X1 f -X3713(,)X -X3761(vol.)X -X3911(20,)X -X875 2268(no.)N -X995(2,)X -X1075(pp.)X -X1195(85-113,)X -X1462(June)X -X1629(1988.)X -X -X4 p -X%%Trailer -Xxt -X -Xxs -END_OF_FILE -if test 33302 -ne `wc -c <'readme.ps'`; then - echo shar: \"'readme.ps'\" unpacked with wrong size! -fi -# end of 'readme.ps' -fi -if test -f 'sdbm.3' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'sdbm.3'\" -else -echo shar: Extracting \"'sdbm.3'\" \(8952 characters\) -sed "s/^X//" >'sdbm.3' <<'END_OF_FILE' -X.\" $Id: sdbm.3,v 1.2 90/12/13 13:00:57 oz Exp $ -X.TH SDBM 3 "1 March 1990" -X.SH NAME -Xsdbm, dbm_open, dbm_prep, dbm_close, dbm_fetch, dbm_store, dbm_delete, dbm_firstkey, dbm_nextkey, dbm_hash, dbm_rdonly, dbm_error, dbm_clearerr, dbm_dirfno, dbm_pagfno \- data base subroutines -X.SH SYNOPSIS -X.nf -X.ft B -X#include <sdbm.h> -X.sp -Xtypedef struct { -X char *dptr; -X int dsize; -X} datum; -X.sp -Xdatum nullitem = { NULL, 0 }; -X.sp -X\s-1DBM\s0 *dbm_open(char *file, int flags, int mode) -X.sp -X\s-1DBM\s0 *dbm_prep(char *dirname, char *pagname, int flags, int mode) -X.sp -Xvoid dbm_close(\s-1DBM\s0 *db) -X.sp -Xdatum dbm_fetch(\s-1DBM\s0 *db, key) -X.sp -Xint dbm_store(\s-1DBM\s0 *db, datum key, datum val, int flags) -X.sp -Xint dbm_delete(\s-1DBM\s0 *db, datum key) -X.sp -Xdatum dbm_firstkey(\s-1DBM\s0 *db) -X.sp -Xdatum dbm_nextkey(\s-1DBM\s0 *db) -X.sp -Xlong dbm_hash(char *string, int len) -X.sp -Xint dbm_rdonly(\s-1DBM\s0 *db) -Xint dbm_error(\s-1DBM\s0 *db) -Xdbm_clearerr(\s-1DBM\s0 *db) -Xint dbm_dirfno(\s-1DBM\s0 *db) -Xint dbm_pagfno(\s-1DBM\s0 *db) -X.ft R -X.fi -X.SH DESCRIPTION -X.IX "database library" sdbm "" "\fLsdbm\fR" -X.IX dbm_open "" "\fLdbm_open\fR \(em open \fLsdbm\fR database" -X.IX dbm_prep "" "\fLdbm_prep\fR \(em prepare \fLsdbm\fR database" -X.IX dbm_close "" "\fLdbm_close\fR \(em close \fLsdbm\fR routine" -X.IX dbm_fetch "" "\fLdbm_fetch\fR \(em fetch \fLsdbm\fR database data" -X.IX dbm_store "" "\fLdbm_store\fR \(em add data to \fLsdbm\fR database" -X.IX dbm_delete "" "\fLdbm_delete\fR \(em remove data from \fLsdbm\fR database" -X.IX dbm_firstkey "" "\fLdbm_firstkey\fR \(em access \fLsdbm\fR database" -X.IX dbm_nextkey "" "\fLdbm_nextkey\fR \(em access \fLsdbm\fR database" -X.IX dbm_hash "" "\fLdbm_hash\fR \(em string hash for \fLsdbm\fR database" -X.IX dbm_rdonly "" "\fLdbm_rdonly\fR \(em return \fLsdbm\fR database read-only mode" -X.IX dbm_error "" "\fLdbm_error\fR \(em return \fLsdbm\fR database error condition" -X.IX dbm_clearerr "" "\fLdbm_clearerr\fR \(em clear \fLsdbm\fR database error condition" -X.IX dbm_dirfno "" "\fLdbm_dirfno\fR \(em return \fLsdbm\fR database bitmap file descriptor" -X.IX dbm_pagfno "" "\fLdbm_pagfno\fR \(em return \fLsdbm\fR database data file descriptor" -X.IX "database functions \(em \fLsdbm\fR" dbm_open "" \fLdbm_open\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_prep "" \fLdbm_prep\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_close "" \fLdbm_close\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_fetch "" \fLdbm_fetch\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_store "" \fLdbm_store\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_delete "" \fLdbm_delete\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_firstkey "" \fLdbm_firstkey\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_nextkey "" \fLdbm_nextkey\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_rdonly "" \fLdbm_rdonly\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_error "" \fLdbm_error\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_clearerr "" \fLdbm_clearerr\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_dirfno "" \fLdbm_dirfno\fP -X.IX "database functions \(em \fLsdbm\fR" dbm_pagfno "" \fLdbm_pagfno\fP -X.LP -XThis package allows an application to maintain a mapping of <key,value> pairs -Xin disk files. This is not to be considered a real database system, but is -Xstill useful in many simple applications built around fast retrieval of a data -Xvalue from a key. This implementation uses an external hashing scheme, -Xcalled Dynamic Hashing, as described by Per-Aake Larson in BIT 18 (1978) pp. -X184-201. Retrieval of any item usually requires a single disk access. -XThe application interface is compatible with the -X.IR ndbm (3) -Xlibrary. -X.LP -XAn -X.B sdbm -Xdatabase is kept in two files usually given the extensions -X.B \.dir -Xand -X.BR \.pag . -XThe -X.B \.dir -Xfile contains a bitmap representing a forest of binary hash trees, the leaves -Xof which indicate data pages in the -X.B \.pag -Xfile. -X.LP -XThe application interface uses the -X.B datum -Xstructure to describe both -X.I keys -Xand -X.IR value s. -XA -X.B datum -Xspecifies a byte sequence of -X.I dsize -Xsize pointed to by -X.IR dptr . -XIf you use -X.SM ASCII -Xstrings as -X.IR key s -Xor -X.IR value s, -Xthen you must decide whether or not to include the terminating -X.SM NUL -Xbyte which sometimes defines strings. Including it will require larger -Xdatabase files, but it will be possible to get sensible output from a -X.IR strings (1) -Xcommand applied to the data file. -X.LP -XIn order to allow a process using this package to manipulate multiple -Xdatabases, the applications interface always requires a -X.IR handle , -Xa -X.BR "DBM *" , -Xto identify the database to be manipulated. Such a handle can be obtained -Xfrom the only routines that do not require it, namely -X.BR dbm_open (\|) -Xor -X.BR dbm_prep (\|). -XEither of these will open or create the two necessary files. The -Xdifference is that the latter allows explicitly naming the bitmap and data -Xfiles whereas -X.BR dbm_open (\|) -Xwill take a base file name and call -X.BR dbm_prep (\|) -Xwith the default extensions. -XThe -X.I flags -Xand -X.I mode -Xparameters are the same as for -X.BR open (2). -X.LP -XTo free the resources occupied while a database handle is active, call -X.BR dbm_close (\|). -X.LP -XGiven a handle, one can retrieve data associated with a key by using the -X.BR dbm_fetch (\|) -Xroutine, and associate data with a key by using the -X.BR dbm_store (\|) -Xroutine. -X.LP -XThe values of the -X.I flags -Xparameter for -X.BR dbm_store (\|) -Xcan be either -X.BR \s-1DBM_INSERT\s0 , -Xwhich will not change an existing entry with the same key, or -X.BR \s-1DBM_REPLACE\s0 , -Xwhich will replace an existing entry with the same key. -XKeys are unique within the database. -X.LP -XTo delete a key and its associated value use the -X.BR dbm_delete (\|) -Xroutine. -X.LP -XTo retrieve every key in the database, use a loop like: -X.sp -X.nf -X.ft B -Xfor (key = dbm_firstkey(db); key.dptr != NULL; key = dbm_nextkey(db)) -X ; -X.ft R -X.fi -X.LP -XThe order of retrieval is unspecified. -X.LP -XIf you determine that the performance of the database is inadequate or -Xyou notice clustering or other effects that may be due to the hashing -Xalgorithm used by this package, you can override it by supplying your -Xown -X.BR dbm_hash (\|) -Xroutine. Doing so will make the database unintelligable to any other -Xapplications that do not use your specialized hash function. -X.sp -X.LP -XThe following macros are defined in the header file: -X.IP -X.BR dbm_rdonly (\|) -Xreturns true if the database has been opened read\-only. -X.IP -X.BR dbm_error (\|) -Xreturns true if an I/O error has occurred. -X.IP -X.BR dbm_clearerr (\|) -Xallows you to clear the error flag if you think you know what the error -Xwas and insist on ignoring it. -X.IP -X.BR dbm_dirfno (\|) -Xreturns the file descriptor associated with the bitmap file. -X.IP -X.BR dbm_pagfno (\|) -Xreturns the file descriptor associated with the data file. -X.SH SEE ALSO -X.IR open (2). -X.SH DIAGNOSTICS -XFunctions that return a -X.B "DBM *" -Xhandle will use -X.SM NULL -Xto indicate an error. -XFunctions that return an -X.B int -Xwill use \-1 to indicate an error. The normal return value in that case is 0. -XFunctions that return a -X.B datum -Xwill return -X.B nullitem -Xto indicate an error. -X.LP -XAs a special case of -X.BR dbm_store (\|), -Xif it is called with the -X.B \s-1DBM_INSERT\s0 -Xflag and the key already exists in the database, the return value will be 1. -X.LP -XIn general, if a function parameter is invalid, -X.B errno -Xwill be set to -X.BR \s-1EINVAL\s0 . -XIf a write operation is requested on a read-only database, -X.B errno -Xwill be set to -X.BR \s-1ENOPERM\s0 . -XIf a memory allocation (using -X.IR malloc (3)) -Xfailed, -X.B errno -Xwill be set to -X.BR \s-1ENOMEM\s0 . -XFor I/O operation failures -X.B errno -Xwill contain the value set by the relevant failed system call, either -X.IR read (2), -X.IR write (2), -Xor -X.IR lseek (2). -X.SH AUTHOR -X.IP "Ozan S. Yigit" (oz@nexus.yorku.ca) -X.SH BUGS -XThe sum of key and value data sizes must not exceed -X.B \s-1PAIRMAX\s0 -X(1008 bytes). -X.LP -XThe sum of the key and value data sizes where several keys hash to the -Xsame value must fit within one bitmap page. -X.LP -XThe -X.B \.pag -Xfile will contain holes, so its apparent size is larger than its contents. -XWhen copied through the filesystem the holes will be filled. -X.LP -XThe contents of -X.B datum -Xvalues returned are in volatile storage. If you want to retain the values -Xpointed to, you must copy them immediately before another call to this package. -X.LP -XThe only safe way for multiple processes to (read and) update a database at -Xthe same time, is to implement a private locking scheme outside this package -Xand open and close the database between lock acquisitions. It is safe for -Xmultiple processes to concurrently access a database read-only. -X.SH APPLICATIONS PORTABILITY -XFor complete source code compatibility with the Berkeley Unix -X.IR ndbm (3) -Xlibrary, the -X.B sdbm.h -Xheader file should be installed in -X.BR /usr/include/ndbm.h . -X.LP -XThe -X.B nullitem -Xdata item, and the -X.BR dbm_prep (\|), -X.BR dbm_hash (\|), -X.BR dbm_rdonly (\|), -X.BR dbm_dirfno (\|), -Xand -X.BR dbm_pagfno (\|) -Xfunctions are unique to this package. -END_OF_FILE -if test 8952 -ne `wc -c <'sdbm.3'`; then - echo shar: \"'sdbm.3'\" unpacked with wrong size! -fi -# end of 'sdbm.3' -fi -if test -f 'sdbm.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'sdbm.c'\" -else -echo shar: Extracting \"'sdbm.c'\" \(11029 characters\) -sed "s/^X//" >'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 if needed. -X */ -X if (flags & O_WRONLY) -X flags = (flags & ~O_WRONLY) | O_RDWR; -X -X else if ((flags & 03) == 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 11029 -ne `wc -c <'sdbm.c'`; then - echo shar: \"'sdbm.c'\" unpacked with wrong size! -fi -# end of 'sdbm.c' -fi -if test -f 'sdbm.h' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'sdbm.h'\" -else -echo shar: Extracting \"'sdbm.h'\" \(2174 characters\) -sed "s/^X//" >'sdbm.h' <<'END_OF_FILE' -X/* -X * sdbm - ndbm work-alike hashed database library -X * based on Per-Ake Larson's Dynamic Hashing algorithms. BIT 18 (1978). -X * author: oz@nexus.yorku.ca -X * status: public domain. -X */ -X#define DBLKSIZ 4096 -X#define PBLKSIZ 1024 -X#define PAIRMAX 1008 /* arbitrary on PBLKSIZ-N */ -X#define SPLTMAX 10 /* maximum allowed splits */ -X /* for a single insertion */ -X#define DIRFEXT ".dir" -X#define PAGFEXT ".pag" -X -Xtypedef struct { -X int dirf; /* directory file descriptor */ -X int pagf; /* page file descriptor */ -X int flags; /* status/error flags, see below */ -X long maxbno; /* size of dirfile in bits */ -X long curbit; /* current bit number */ -X long hmask; /* current hash mask */ -X long blkptr; /* current block for nextkey */ -X int keyptr; /* current key for nextkey */ -X long blkno; /* current page to read/write */ -X long pagbno; /* current page in pagbuf */ -X char pagbuf[PBLKSIZ]; /* page file block buffer */ -X long dirbno; /* current block in dirbuf */ -X char dirbuf[DBLKSIZ]; /* directory file block buffer */ -X} DBM; -X -X#define DBM_RDONLY 0x1 /* data base open read-only */ -X#define DBM_IOERR 0x2 /* data base I/O error */ -X -X/* -X * utility macros -X */ -X#define dbm_rdonly(db) ((db)->flags & DBM_RDONLY) -X#define dbm_error(db) ((db)->flags & DBM_IOERR) -X -X#define dbm_clearerr(db) ((db)->flags &= ~DBM_IOERR) /* ouch */ -X -X#define dbm_dirfno(db) ((db)->dirf) -X#define dbm_pagfno(db) ((db)->pagf) -X -Xtypedef struct { -X char *dptr; -X int dsize; -X} datum; -X -Xextern datum nullitem; -X -X#ifdef __STDC__ -X#define proto(p) p -X#else -X#define proto(p) () -X#endif -X -X/* -X * flags to dbm_store -X */ -X#define DBM_INSERT 0 -X#define DBM_REPLACE 1 -X -X/* -X * ndbm interface -X */ -Xextern DBM *dbm_open proto((char *, int, int)); -Xextern void dbm_close proto((DBM *)); -Xextern datum dbm_fetch proto((DBM *, datum)); -Xextern int dbm_delete proto((DBM *, datum)); -Xextern int dbm_store proto((DBM *, datum, datum, int)); -Xextern datum dbm_firstkey proto((DBM *)); -Xextern datum dbm_nextkey proto((DBM *)); -X -X/* -X * other -X */ -Xextern DBM *dbm_prep proto((char *, char *, int, int)); -Xextern long dbm_hash proto((char *, int)); -END_OF_FILE -if test 2174 -ne `wc -c <'sdbm.h'`; then - echo shar: \"'sdbm.h'\" unpacked with wrong size! -fi -# end of 'sdbm.h' -fi -if test -f 'tune.h' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'tune.h'\" -else -echo shar: Extracting \"'tune.h'\" \(665 characters\) -sed "s/^X//" >'tune.h' <<'END_OF_FILE' -X/* -X * sdbm - ndbm work-alike hashed database library -X * tuning and portability constructs [not nearly enough] -X * author: oz@nexus.yorku.ca -X */ -X -X#define BYTESIZ 8 -X -X#ifdef SVID -X#include <unistd.h> -X#endif -X -X#ifdef BSD42 -X#define SEEK_SET L_SET -X#define memset(s,c,n) bzero(s, n) /* only when c is zero */ -X#define memcpy(s1,s2,n) bcopy(s2, s1, n) -X#define memcmp(s1,s2,n) bcmp(s1,s2,n) -X#endif -X -X/* -X * important tuning parms (hah) -X */ -X -X#define SEEDUPS /* always detect duplicates */ -X#define BADMESS /* generate a message for worst case: -X cannot make room after SPLTMAX splits */ -X/* -X * misc -X */ -X#ifdef DEBUG -X#define debug(x) printf x -X#else -X#define debug(x) -X#endif -END_OF_FILE -if test 665 -ne `wc -c <'tune.h'`; then - echo shar: \"'tune.h'\" unpacked with wrong size! -fi -# end of 'tune.h' -fi -if test -f 'util.c' -a "${1}" != "-c" ; then - echo shar: Will not clobber existing file \"'util.c'\" -else -echo shar: Extracting \"'util.c'\" \(767 characters\) -sed "s/^X//" >'util.c' <<'END_OF_FILE' -X#include <stdio.h> -X#ifdef SDBM -X#include "sdbm.h" -X#else -X#include "ndbm.h" -X#endif -X -Xvoid -Xoops(s1, s2) -Xregister char *s1; -Xregister char *s2; -X{ -X extern int errno, sys_nerr; -X extern char *sys_errlist[]; -X extern char *progname; -X -X if (progname) -X fprintf(stderr, "%s: ", progname); -X fprintf(stderr, s1, s2); -X if (errno > 0 && errno < sys_nerr) -X fprintf(stderr, " (%s)", sys_errlist[errno]); -X fprintf(stderr, "\n"); -X exit(1); -X} -X -Xint -Xokpage(pag) -Xchar *pag; -X{ -X register unsigned n; -X register off; -X register short *ino = (short *) pag; -X -X if ((n = ino[0]) > PBLKSIZ / sizeof(short)) -X return 0; -X -X if (!n) -X return 1; -X -X off = PBLKSIZ; -X for (ino++; n; ino += 2) { -X if (ino[0] > off || ino[1] > off || -X ino[1] > ino[0]) -X return 0; -X off = ino[1]; -X n -= 2; -X } -X -X return 1; -X} -END_OF_FILE -if test 767 -ne `wc -c <'util.c'`; then - echo shar: \"'util.c'\" unpacked with wrong size! -fi -# end of 'util.c' -fi -echo shar: End of shell archive. -exit 0 |