diff options
Diffstat (limited to 'ext/SDBM_File/sdbm')
26 files changed, 5945 insertions, 0 deletions
diff --git a/ext/SDBM_File/sdbm/CHANGES b/ext/SDBM_File/sdbm/CHANGES new file mode 100644 index 0000000000..f7296d1b3a --- /dev/null +++ b/ext/SDBM_File/sdbm/CHANGES @@ -0,0 +1,18 @@ +Changes from the earlier BETA releases. + +o dbm_prep does everything now, so dbm_open is just a simple + wrapper that builds the default filenames. dbm_prep no longer + requires a (DBM *) db parameter: it allocates one itself. It + returns (DBM *) db or (DBM *) NULL. + +o makroom is now reliable. In the common-case optimization of the page + split, the page into which the incoming key/value pair is to be inserted + is write-deferred (if the split is successful), thereby saving a cosly + write. BUT, if the split does not make enough room (unsuccessful), the + deferred page is written out, as the failure-window is now dependent on + the number of split attempts. + +o if -DDUFF is defined, hash function will also use the DUFF construct. + This may look like a micro-performance tweak (maybe it is), but in fact, + the hash function is the third most-heavily used function, after read + and write. diff --git a/ext/SDBM_File/sdbm/COMPARE b/ext/SDBM_File/sdbm/COMPARE new file mode 100644 index 0000000000..a595e831d2 --- /dev/null +++ b/ext/SDBM_File/sdbm/COMPARE @@ -0,0 +1,88 @@ + +Script started on Thu Sep 28 15:41:06 1989 +% uname -a +titan titan 4_0 UMIPS mips +% make all x-dbm + cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dbm.c + cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c sdbm.c + cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c pair.c + cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c hash.c + ar cr libsdbm.a sdbm.o pair.o hash.o + ranlib libsdbm.a + cc -o dbm dbm.o libsdbm.a + cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dba.c + cc -o dba dba.o + cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dbd.c + cc -o dbd dbd.o + cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -o x-dbm dbm.o +% +% +% wc history + 65110 218344 3204883 history +% +% /bin/time dbm build foo <history + +real 5:56.9 +user 13.3 +sys 26.3 +% ls -s +total 14251 + 5 README 2 dbd.c 1 hash.c 1 pair.h + 0 SCRIPT 5 dbd.o 1 hash.o 5 pair.o + 1 WISHLIST 62 dbm 3130 history 1 port.h + 46 dba 5 dbm.c 11 howtodbm.txt 11 sdbm.c + 3 dba.c 8 dbm.o 14 libsdbm.a 2 sdbm.h + 6 dba.o 4 foo.dir 1 makefile 8 sdbm.o + 46 dbd 10810 foo.pag 6 pair.c 60 x-dbm +% ls -l foo.* +-rw-r--r-- 1 oz 4096 Sep 28 15:48 foo.dir +-rw-r--r-- 1 oz 11069440 Sep 28 15:48 foo.pag +% +% /bin/time x-dbm build bar <history + +real 5:59.4 +user 24.7 +sys 29.1 +% +% ls -s +total 27612 + 5 README 46 dbd 1 hash.c 5 pair.o + 1 SCRIPT 2 dbd.c 1 hash.o 1 port.h + 1 WISHLIST 5 dbd.o 3130 history 11 sdbm.c + 4 bar.dir 62 dbm 11 howtodbm.txt 2 sdbm.h +13356 bar.pag 5 dbm.c 14 libsdbm.a 8 sdbm.o + 46 dba 8 dbm.o 1 makefile 60 x-dbm + 3 dba.c 4 foo.dir 6 pair.c + 6 dba.o 10810 foo.pag 1 pair.h +% +% ls -l bar.* +-rw-r--r-- 1 oz 4096 Sep 28 15:54 bar.dir +-rw-r--r-- 1 oz 13676544 Sep 28 15:54 bar.pag +% +% dba foo | tail +#10801: ok. no entries. +#10802: ok. no entries. +#10803: ok. no entries. +#10804: ok. no entries. +#10805: ok. no entries. +#10806: ok. no entries. +#10807: ok. no entries. +#10808: ok. no entries. +#10809: ok. 11 entries 67% used free 337. +10810 pages (6036 holes): 65073 entries +% +% dba bar | tail +#13347: ok. no entries. +#13348: ok. no entries. +#13349: ok. no entries. +#13350: ok. no entries. +#13351: ok. no entries. +#13352: ok. no entries. +#13353: ok. no entries. +#13354: ok. no entries. +#13355: ok. 7 entries 33% used free 676. +13356 pages (8643 holes): 65073 entries +% +% exit +script done on Thu Sep 28 16:08:45 1989 + diff --git a/ext/SDBM_File/sdbm/Makefile.SH b/ext/SDBM_File/sdbm/Makefile.SH new file mode 100644 index 0000000000..521c97270a --- /dev/null +++ b/ext/SDBM_File/sdbm/Makefile.SH @@ -0,0 +1,99 @@ +: This forces SH files to create target in same directory as SH file. +: This is so that make depend always knows where to find SH derivatives. + +case "$0" in +*/*) cd `expr X$0 : 'X\(.*\)/'` ;; +esac + +if test -f config.sh; then TOP=.; +elif test -f ../config.sh; then TOP=..; +elif test -f ../../config.sh; then TOP=../..; +elif test -f ../../../config.sh; then TOP=../../..; +elif test -f ../../../../config.sh; then TOP=../../../..; +else + echo "Can't find config.sh."; exit 1 +fi + +: Find absolute path name for TOP. This is needed when we cd to TOP +: to run perl on autosplit. +oldpwd=`pwd`; cd $TOP; ABSTOP=`pwd`; cd $oldpwd + +case $CONFIG in +'') + . $TOP/config.sh + ;; +esac + +echo "Extracting ext/SDBM_File/sdbm/Makefile (with variable substitutions)" +: This section of the file will have variable substitutions done on it. +: Move anything that needs config subs from !NO!SUBS! section to !GROK!THIS!. +: Protect any dollar signs and backticks that you do not want interpreted +: by putting a backslash in front. You may delete these comments. +$spitshell >Makefile <<!GROK!THIS! +# +# This Makefile is for the library part of sdbm. For the +# Full package, see makefile.sdbm. +# +# Makefile for public domain ndbm-clone: sdbm +# DUFF: use duff's device (loop unroll) in parts of the code +# +# +CC = $cc +RANLIB = $ranlib +TOP = $TOP +ABSTOP = $ABSTOP +LDFLAGS = $ldflags +CLDFLAGS = $ldflags +SMALL = $small +LARGE = $large $split + +# To use an alternate make, set \$altmake in config.sh. +MAKE = ${altmake-make} + +# The following are used to build and install shared libraries for +# dynamic loading. +LDDLFLAGS = $lddlflags +CCDLFLAGS = $ccdlflags +CCCDLFLAGS = $cccdlflags + +!GROK!THIS! + +: In the following dollars and backticks do not need the extra backslash. +$spitshell >>Makefile <<'!NO!SUBS!' +SHELL = /bin/sh +CCCMD = `sh $(shellflags) $(TOP)/cflags $@` + +.c.o: + $(CCCMD) $(CCCDLFLAGS) -I$(TOP) -DSDBM -DDUFF $*.c + +LIBOBJS = sdbm.o pair.o hash.o +LIBSRCS = sdbm.c pair.c hash.c +HDRS = tune.h sdbm.h pair.h $(TOP)/config.h + +all: libsdbm.a + +libsdbm.a: $(LIBOBJS) + ar cr libsdbm.a $(LIBOBJS) + $(RANLIB) libsdbm.a + +$(LIBOBJS): $(HDRS) + +lint: + lint -abchx $(LIBSRCS) + +clean: + rm -f *.o *.a mon.out core + +realclean: clean + rm -f dbu libsdbm.a dbd dba dbe x-dbu *.dir *.pag + rm -f makefile Makefile + +purge: realclean + +sdbm.o : sdbm.c $(TOP)/config.h sdbm.h tune.h pair.h +hash.o : hash.c $(TOP)/config.h sdbm.h +pair.o : pair.c $(TOP)/config.h sdbm.h tune.h pair.h + +!NO!SUBS! +chmod 755 Makefile +$eunicefix Makefile diff --git a/ext/SDBM_File/sdbm/README b/ext/SDBM_File/sdbm/README new file mode 100644 index 0000000000..cd7312cc57 --- /dev/null +++ b/ext/SDBM_File/sdbm/README @@ -0,0 +1,396 @@ + + + + + + + sdbm - Substitute DBM + or + Berkeley ndbm for Every UN*X[1] Made Simple + + Ozan (oz) Yigit + + The Guild of PD Software Toolmakers + Toronto - Canada + + oz@nexus.yorku.ca + + + +Implementation is the sincerest form of flattery. - L. Peter +Deutsch + +A The Clone of the ndbm library + + The sources accompanying this notice - sdbm - consti- +tute the first public release (Dec. 1990) of a complete +clone of the Berkeley UN*X ndbm library. The sdbm library is +meant to clone the proven functionality of ndbm as closely +as possible, including a few improvements. It is practical, +easy to understand, and compatible. The sdbm library is not +derived from any licensed, proprietary or copyrighted +software. + + The sdbm implementation is based on a 1978 algorithm +[Lar78] by P.-A. (Paul) Larson known as ``Dynamic Hashing''. +In the course of searching for a substitute for ndbm, I pro- +totyped three different external-hashing algorithms [Lar78, +Fag79, Lit80] and ultimately chose Larson's algorithm as a +basis of the sdbm implementation. The Bell Labs dbm (and +therefore ndbm) is based on an algorithm invented by Ken +Thompson, [Tho90, Tor87] and predates Larson's work. + + The sdbm programming interface is totally compatible +with ndbm and includes a slight improvement in database ini- +tialization. It is also expected to be binary-compatible +under most UN*X versions that support the ndbm library. + + The sdbm implementation shares the shortcomings of the +ndbm library, as a side effect of various simplifications to +the original Larson algorithm. It does produce holes in the +page file as it writes pages past the end of file. (Larson's +paper include a clever solution to this problem that is a +result of using the hash value directly as a block address.) +On the other hand, extensive tests seem to indicate that +sdbm creates fewer holes in general, and the resulting page- +files are smaller. The sdbm implementation is also faster +than ndbm in database creation. Unlike the ndbm, the sdbm +_________________________ + + [1] UN*X is not a trademark of any (dis)organization. + + + + + + + + + + - 2 - + + +store operation will not ``wander away'' trying to split its +data pages to insert a datum that cannot (due to elaborate +worst-case situations) be inserted. (It will fail after a +pre-defined number of attempts.) + +Important Compatibility Warning + + The sdbm and ndbm libraries cannot share databases: one +cannot read the (dir/pag) database created by the other. +This is due to the differences between the ndbm and sdbm +algorithms[2], and the hash functions used. It is easy to +convert between the dbm/ndbm databases and sdbm by ignoring +the index completely: see dbd, dbu etc. + + +Notice of Intellectual Property + +The entire sdbm library package, as authored by me, Ozan S. +Yigit, is hereby placed in the public domain. As such, the +author is not responsible for the consequences of use of +this software, no matter how awful, even if they arise from +defects in it. There is no expressed or implied warranty for +the sdbm library. + + Since the sdbm library package is in the public domain, +this original release or any additional public-domain +releases of the modified original cannot possibly (by defin- +ition) be withheld from you. Also by definition, You (singu- +lar) have all the rights to this code (including the right +to sell without permission, the right to hoard[3] and the +right to do other icky things as you see fit) but those +rights are also granted to everyone else. + + Please note that all previous distributions of this +software contained a copyright (which is now dropped) to +protect its origins and its current public domain status +against any possible claims and/or challenges. + +Acknowledgments + + Many people have been very helpful and supportive. A +partial list would necessarily include Rayan Zacherissen +(who contributed the man page, and also hacked a MMAP +_________________________ + + [2] Torek's discussion [Tor87] indicates that +dbm/ndbm implementations use the hash value to traverse +the radix trie differently than sdbm and as a result, +the page indexes are generated in different order. For +more information, send e-mail to the author. + [3] You cannot really hoard something that is avail- +able to the public at large, but try if it makes you +feel any better. + + + + + + + + + + + - 3 - + + +version of sdbm), Arnold Robbins, Chris Lewis, Bill David- +sen, Henry Spencer, Geoff Collyer, Rich Salz (who got me +started in the first place), Johannes Ruschein (who did the +minix port) and David Tilbrook. I thank you all. + +Distribution Manifest and Notes + +This distribution of sdbm includes (at least) the following: + + CHANGES change log + README this file. + biblio a small bibliography on external hashing + dba.c a crude (n/s)dbm page file analyzer + dbd.c a crude (n/s)dbm page file dumper (for conversion) + dbe.1 man page for dbe.c + dbe.c Janick's database editor + dbm.c a dbm library emulation wrapper for ndbm/sdbm + dbm.h header file for the above + dbu.c a crude db management utility + hash.c hashing function + makefile guess. + pair.c page-level routines (posted earlier) + pair.h header file for the above + readme.ms troff source for the README file + sdbm.3 man page + sdbm.c the real thing + sdbm.h header file for the above + tune.h place for tuning & portability thingies + util.c miscellaneous + + dbu is a simple database manipulation program[4] that +tries to look like Bell Labs' cbt utility. It is currently +incomplete in functionality. I use dbu to test out the rou- +tines: it takes (from stdin) tab separated key/value pairs +for commands like build or insert or takes keys for commands +like delete or look. + + dbu <build|creat|look|insert|cat|delete> dbmfile + + dba is a crude analyzer of dbm/sdbm/ndbm page files. It +scans the entire page file, reporting page level statistics, +and totals at the end. + + dbd is a crude dump program for dbm/ndbm/sdbm data- +bases. It ignores the bitmap, and dumps the data pages in +sequence. It can be used to create input for the dbu util- +ity. Note that dbd will skip any NULLs in the key and data +fields, thus is unsuitable to convert some peculiar +_________________________ + + [4] The dbd, dba, dbu utilities are quick hacks and +are not fit for production use. They were developed +late one night, just to test out sdbm, and convert some +databases. + + + + + + + + + + - 4 - + + +databases that insist in including the terminating null. + + I have also included a copy of the dbe (ndbm DataBase +Editor) by Janick Bergeron [janick@bnr.ca] for your pleas- +ure. You may find it more useful than the little dbu util- +ity. + + dbm.[ch] is a dbm library emulation on top of ndbm (and +hence suitable for sdbm). Written by Robert Elz. + + The sdbm library has been around in beta test for quite +a long time, and from whatever little feedback I received +(maybe no news is good news), I believe it has been func- +tioning without any significant problems. I would, of +course, appreciate all fixes and/or improvements. Portabil- +ity enhancements would especially be useful. + +Implementation Issues + + Hash functions: The algorithm behind sdbm implementa- +tion needs a good bit-scrambling hash function to be effec- +tive. I ran into a set of constants for a simple hash func- +tion that seem to help sdbm perform better than ndbm for +various inputs: + + /* + * polynomial conversion ignoring overflows + * 65599 nice. 65587 even better. + */ + long + dbm_hash(char *str, int len) { + register unsigned long n = 0; + + while (len--) + n = n * 65599 + *str++; + return n; + } + + There may be better hash functions for the purposes of +dynamic hashing. Try your favorite, and check the pagefile. +If it contains too many pages with too many holes, (in rela- +tion to this one for example) or if sdbm simply stops work- +ing (fails after SPLTMAX attempts to split) when you feed +your NEWS history file to it, you probably do not have a +good hashing function. If you do better (for different +types of input), I would like to know about the function you +use. + + Block sizes: It seems (from various tests on a few +machines) that a page file block size PBLKSIZ of 1024 is by +far the best for performance, but this also happens to limit +the size of a key/value pair. Depending on your needs, you +may wish to increase the page size, and also adjust PAIRMAX +(the maximum size of a key/value pair allowed: should always + + + + + + + + + + - 5 - + + +be at least three words smaller than PBLKSIZ.) accordingly. +The system-wide version of the library should probably be +configured with 1024 (distribution default), as this appears +to be sufficient for most common uses of sdbm. + +Portability + + This package has been tested in many different UN*Xes +even including minix, and appears to be reasonably portable. +This does not mean it will port easily to non-UN*X systems. + +Notes and Miscellaneous + + The sdbm is not a very complicated package, at least +not after you familiarize yourself with the literature on +external hashing. There are other interesting algorithms in +existence that ensure (approximately) single-read access to +a data value associated with any key. These are directory- +less schemes such as linear hashing [Lit80] (+ Larson varia- +tions), spiral storage [Mar79] or directory schemes such as +extensible hashing [Fag79] by Fagin et al. I do hope these +sources provide a reasonable playground for experimentation +with other algorithms. See the June 1988 issue of ACM Com- +puting Surveys [Enb88] for an excellent overview of the +field. + +References + + +[Lar78] + P.-A. Larson, ``Dynamic Hashing'', BIT, vol. 18, pp. + 184-201, 1978. + +[Tho90] + Ken Thompson, private communication, Nov. 1990 + +[Lit80] + W. Litwin, `` Linear Hashing: A new tool for file and + table addressing'', Proceedings of the 6th Conference on + Very Large Dabatases (Montreal), pp. 212-223, Very + Large Database Foundation, Saratoga, Calif., 1980. + +[Fag79] + R. Fagin, J. Nievergelt, N. Pippinger, and H. R. + Strong, ``Extendible Hashing - A Fast Access Method for + Dynamic Files'', ACM Trans. Database Syst., vol. 4, + no.3, pp. 315-344, Sept. 1979. + +[Wal84] + Rich Wales, ``Discussion of "dbm" data base system'', + USENET newsgroup unix.wizards, Jan. 1984. + +[Tor87] + Chris Torek, ``Re: dbm.a and ndbm.a archives'', + + + + + + + + + + - 6 - + + + USENET newsgroup comp.unix, 1987. + +[Mar79] + G. N. Martin, ``Spiral Storage: Incrementally Augment- + able Hash Addressed Storage'', Technical Report #27, + University of Varwick, Coventry, U.K., 1979. + +[Enb88] + R. J. Enbody and H. C. Du, ``Dynamic Hashing + Schemes'',ACM Computing Surveys, vol. 20, no. 2, pp. + 85-113, June 1988. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/ext/SDBM_File/sdbm/README.too b/ext/SDBM_File/sdbm/README.too new file mode 100644 index 0000000000..c2d095944d --- /dev/null +++ b/ext/SDBM_File/sdbm/README.too @@ -0,0 +1,9 @@ +This version of sdbm merely has all the dbm_* names translated to sdbm_* +so that we can link ndbm and sdbm into the same executable. (It also has +the bad() macro redefined to allow a zero-length key.) + + +Fri Apr 15 10:15:30 EDT 1994. + +Additional portability/configuration changes for libsdbm by Andy Dougherty +doughera@lafcol.lafayette.edu. diff --git a/ext/SDBM_File/sdbm/biblio b/ext/SDBM_File/sdbm/biblio new file mode 100644 index 0000000000..0be09fa005 --- /dev/null +++ b/ext/SDBM_File/sdbm/biblio @@ -0,0 +1,64 @@ +%A R. J. Enbody +%A H. C. Du +%T Dynamic Hashing Schemes +%J ACM Computing Surveys +%V 20 +%N 2 +%D June 1988 +%P 85-113 +%K surveys + +%A P.-A. Larson +%T Dynamic Hashing +%J BIT +%V 18 +%P 184-201 +%D 1978 +%K dynamic + +%A W. Litwin +%T Linear Hashing: A new tool for file and table addressing +%J Proceedings of the 6th Conference on Very Large Dabatases (Montreal) +%I Very Large Database Foundation +%C Saratoga, Calif. +%P 212-223 +%D 1980 +%K linear + +%A R. Fagin +%A J. Nievergelt +%A N. Pippinger +%A H. R. Strong +%T Extendible Hashing - A Fast Access Method for Dynamic Files +%J ACM Trans. Database Syst. +%V 4 +%N 3 +%D Sept. 1979 +%P 315-344 +%K extend + +%A G. N. Martin +%T Spiral Storage: Incrementally Augmentable Hash Addressed Storage +%J Technical Report #27 +%I University of Varwick +%C Coventry, U.K. +%D 1979 +%K spiral + +%A Chris Torek +%T Re: dbm.a and ndbm.a archives +%B USENET newsgroup comp.unix +%D 1987 +%K torek + +%A Rich Wales +%T Discusson of "dbm" data base system +%B USENET newsgroup unix.wizards +%D Jan. 1984 +%K rich + + + + + + diff --git a/ext/SDBM_File/sdbm/dba.c b/ext/SDBM_File/sdbm/dba.c new file mode 100644 index 0000000000..4f227e5245 --- /dev/null +++ b/ext/SDBM_File/sdbm/dba.c @@ -0,0 +1,84 @@ +/* + * dba dbm analysis/recovery + */ + +#include <stdio.h> +#include <sys/file.h> +#include "sdbm.h" + +char *progname; +extern void oops(); + +int +main(argc, argv) +char **argv; +{ + int n; + char *p; + char *name; + int pagf; + + progname = argv[0]; + + if (p = argv[1]) { + name = (char *) malloc((n = strlen(p)) + 5); + strcpy(name, p); + strcpy(name + n, ".pag"); + + if ((pagf = open(name, O_RDONLY)) < 0) + oops("cannot open %s.", name); + + sdump(pagf); + } + else + oops("usage: %s dbname", progname); + + return 0; +} + +sdump(pagf) +int pagf; +{ + register b; + register n = 0; + register t = 0; + register o = 0; + register e; + char pag[PBLKSIZ]; + + while ((b = read(pagf, pag, PBLKSIZ)) > 0) { + printf("#%d: ", n); + if (!okpage(pag)) + printf("bad\n"); + else { + printf("ok. "); + if (!(e = pagestat(pag))) + o++; + else + t += e; + } + n++; + } + + if (b == 0) + printf("%d pages (%d holes): %d entries\n", n, o, t); + else + oops("read failed: block %d", n); +} + +pagestat(pag) +char *pag; +{ + register n; + register free; + register short *ino = (short *) pag; + + if (!(n = ino[0])) + printf("no entries.\n"); + else { + free = ino[n] - (n + 1) * sizeof(short); + printf("%3d entries %2d%% used free %d.\n", + n / 2, ((PBLKSIZ - free) * 100) / PBLKSIZ, free); + } + return n / 2; +} diff --git a/ext/SDBM_File/sdbm/dbd.c b/ext/SDBM_File/sdbm/dbd.c new file mode 100644 index 0000000000..697a547597 --- /dev/null +++ b/ext/SDBM_File/sdbm/dbd.c @@ -0,0 +1,110 @@ +/* + * dbd - dump a dbm data file + */ + +#include <stdio.h> +#include <sys/file.h> +#include "sdbm.h" + +char *progname; +extern void oops(); + + +#define empty(page) (((short *) page)[0] == 0) + +int +main(argc, argv) +char **argv; +{ + int n; + char *p; + char *name; + int pagf; + + progname = argv[0]; + + if (p = argv[1]) { + name = (char *) malloc((n = strlen(p)) + 5); + strcpy(name, p); + strcpy(name + n, ".pag"); + + if ((pagf = open(name, O_RDONLY)) < 0) + oops("cannot open %s.", name); + + sdump(pagf); + } + else + oops("usage: %s dbname", progname); + return 0; +} + +sdump(pagf) +int pagf; +{ + register r; + register n = 0; + register o = 0; + char pag[PBLKSIZ]; + + while ((r = read(pagf, pag, PBLKSIZ)) > 0) { + if (!okpage(pag)) + fprintf(stderr, "%d: bad page.\n", n); + else if (empty(pag)) + o++; + else + dispage(pag); + n++; + } + + if (r == 0) + fprintf(stderr, "%d pages (%d holes).\n", n, o); + else + oops("read failed: block %d", n); +} + + +#ifdef OLD +dispage(pag) +char *pag; +{ + register i, n; + register off; + register short *ino = (short *) pag; + + off = PBLKSIZ; + for (i = 1; i < ino[0]; i += 2) { + printf("\t[%d]: ", ino[i]); + for (n = ino[i]; n < off; n++) + putchar(pag[n]); + putchar(' '); + off = ino[i]; + printf("[%d]: ", ino[i + 1]); + for (n = ino[i + 1]; n < off; n++) + putchar(pag[n]); + off = ino[i + 1]; + putchar('\n'); + } +} +#else +dispage(pag) +char *pag; +{ + register i, n; + register off; + register short *ino = (short *) pag; + + off = PBLKSIZ; + for (i = 1; i < ino[0]; i += 2) { + for (n = ino[i]; n < off; n++) + if (pag[n] != 0) + putchar(pag[n]); + putchar('\t'); + off = ino[i]; + for (n = ino[i + 1]; n < off; n++) + if (pag[n] != 0) + putchar(pag[n]); + putchar('\n'); + off = ino[i + 1]; + } +} +#endif diff --git a/ext/SDBM_File/sdbm/dbe.1 b/ext/SDBM_File/sdbm/dbe.1 new file mode 100644 index 0000000000..3b32272684 --- /dev/null +++ b/ext/SDBM_File/sdbm/dbe.1 @@ -0,0 +1,46 @@ +.TH dbe 1 "ndbm(3) EDITOR" +.SH NAME +dbe \- Edit a ndbm(3) database +.SH USAGE +dbe <database> [-m r|w|rw] [-crtvx] -a|-d|-f|-F|-s [<key> [<content>]] +.SH DESCRIPTION +\fIdbme\fP operates on ndbm(3) databases. +It can be used to create them, look at them or change them. +When specifying the value of a key or the content of its associated entry, +\\nnn, \\0, \\n, \\t, \\f and \\r are interpreted as usual. +When displaying key/content pairs, non-printable characters are displayed +using the \\nnn notation. +.SH OPTIONS +.IP -a +List all entries in the database. +.IP -c +Create the database if it does not exist. +.IP -d +Delete the entry associated with the specified key. +.IP -f +Fetch and display the entry associated with the specified key. +.IP -F +Fetch and display all the entries whose key match the specified +regular-expression +.IP "-m r|w|rw" +Open the database in read-only, write-only or read-write mode +.IP -r +Replace the entry associated with the specified key if it already exists. +See option -s. +.IP -s +Store an entry under a specific key. +An error occurs if the key already exists and the option -r was not specified. +.IP -t +Re-initialize the database before executing the command. +.IP -v +Verbose mode. +Confirm stores and deletions. +.IP -x +If option -x is used with option -c, then if the database already exists, +an error occurs. +This can be used to implement a simple exclusive access locking mechanism. +.SH SEE ALSO +ndbm(3) +.SH AUTHOR +janick@bnr.ca + diff --git a/ext/SDBM_File/sdbm/dbe.c b/ext/SDBM_File/sdbm/dbe.c new file mode 100644 index 0000000000..2a306f276e --- /dev/null +++ b/ext/SDBM_File/sdbm/dbe.c @@ -0,0 +1,435 @@ +#include <stdio.h> +#ifndef VMS +#include <sys/file.h> +#include <ndbm.h> +#else +#include "file.h" +#include "ndbm.h" +#endif +#include <ctype.h> + +/***************************************************************************\ +** ** +** Function name: getopt() ** +** Author: Henry Spencer, UofT ** +** Coding date: 84/04/28 ** +** ** +** Description: ** +** ** +** Parses argv[] for arguments. ** +** Works with Whitesmith's C compiler. ** +** ** +** Inputs - The number of arguments ** +** - The base address of the array of arguments ** +** - A string listing the valid options (':' indicates an ** +** argument to the preceding option is required, a ';' ** +** indicates an argument to the preceding option is optional) ** +** ** +** Outputs - Returns the next option character, ** +** '?' for non '-' arguments ** +** or ':' when there is no more arguments. ** +** ** +** Side Effects + The argument to an option is pointed to by 'optarg' ** +** ** +***************************************************************************** +** ** +** REVISION HISTORY: ** +** ** +** DATE NAME DESCRIPTION ** +** YY/MM/DD ------------------ ------------------------------------ ** +** 88/10/20 Janick Bergeron Returns '?' on unamed arguments ** +** returns '!' on unknown options ** +** and 'EOF' only when exhausted. ** +** 88/11/18 Janick Bergeron Return ':' when no more arguments ** +** 89/08/11 Janick Bergeron Optional optarg when ';' in optstring ** +** ** +\***************************************************************************/ + +char *optarg; /* Global argument pointer. */ + +#ifdef VMS +#define index strchr +#endif + +char +getopt(argc, argv, optstring) +int argc; +char **argv; +char *optstring; +{ + register int c; + register char *place; + extern char *index(); + static int optind = 0; + static char *scan = NULL; + + optarg = NULL; + + if (scan == NULL || *scan == '\0') { + + if (optind == 0) + optind++; + if (optind >= argc) + return ':'; + + optarg = place = argv[optind++]; + if (place[0] != '-' || place[1] == '\0') + return '?'; + if (place[1] == '-' && place[2] == '\0') + return '?'; + scan = place + 1; + } + + c = *scan++; + place = index(optstring, c); + if (place == NULL || c == ':' || c == ';') { + + (void) fprintf(stderr, "%s: unknown option %c\n", argv[0], c); + scan = NULL; + return '!'; + } + if (*++place == ':') { + + if (*scan != '\0') { + + optarg = scan; + scan = NULL; + + } + else { + + if (optind >= argc) { + + (void) fprintf(stderr, "%s: %c requires an argument\n", + argv[0], c); + return '!'; + } + optarg = argv[optind]; + optind++; + } + } + else if (*place == ';') { + + if (*scan != '\0') { + + optarg = scan; + scan = NULL; + + } + else { + + if (optind >= argc || *argv[optind] == '-') + optarg = NULL; + else { + optarg = argv[optind]; + optind++; + } + } + } + return c; +} + + +void +print_datum(db) +datum db; +{ + int i; + + putchar('"'); + for (i = 0; i < db.dsize; i++) { + if (isprint(db.dptr[i])) + putchar(db.dptr[i]); + else { + putchar('\\'); + putchar('0' + ((db.dptr[i] >> 6) & 0x07)); + putchar('0' + ((db.dptr[i] >> 3) & 0x07)); + putchar('0' + (db.dptr[i] & 0x07)); + } + } + putchar('"'); +} + + +datum +read_datum(s) +char *s; +{ + datum db; + char *p; + int i; + + db.dsize = 0; + db.dptr = (char *) malloc(strlen(s) * sizeof(char)); + for (p = db.dptr; *s != '\0'; p++, db.dsize++, s++) { + if (*s == '\\') { + if (*++s == 'n') + *p = '\n'; + else if (*s == 'r') + *p = '\r'; + else if (*s == 'f') + *p = '\f'; + else if (*s == 't') + *p = '\t'; + else if (isdigit(*s) && isdigit(*(s + 1)) && isdigit(*(s + 2))) { + i = (*s++ - '0') << 6; + i |= (*s++ - '0') << 3; + i |= *s - '0'; + *p = i; + } + else if (*s == '0') + *p = '\0'; + else + *p = *s; + } + else + *p = *s; + } + + return db; +} + + +char * +key2s(db) +datum db; +{ + char *buf; + char *p1, *p2; + + buf = (char *) malloc((db.dsize + 1) * sizeof(char)); + for (p1 = buf, p2 = db.dptr; *p2 != '\0'; *p1++ = *p2++); + *p1 = '\0'; + return buf; +} + + +main(argc, argv) +int argc; +char **argv; +{ + typedef enum { + YOW, FETCH, STORE, DELETE, SCAN, REGEXP + } commands; + char opt; + int flags; + int giveusage = 0; + int verbose = 0; + commands what = YOW; + char *comarg[3]; + int st_flag = DBM_INSERT; + int argn; + DBM *db; + datum key; + datum content; + + flags = O_RDWR; + argn = 0; + + while ((opt = getopt(argc, argv, "acdfFm:rstvx")) != ':') { + switch (opt) { + case 'a': + what = SCAN; + break; + case 'c': + flags |= O_CREAT; + break; + case 'd': + what = DELETE; + break; + case 'f': + what = FETCH; + break; + case 'F': + what = REGEXP; + break; + case 'm': + flags &= ~(000007); + if (strcmp(optarg, "r") == 0) + flags |= O_RDONLY; + else if (strcmp(optarg, "w") == 0) + flags |= O_WRONLY; + else if (strcmp(optarg, "rw") == 0) + flags |= O_RDWR; + else { + fprintf(stderr, "Invalid mode: \"%s\"\n", optarg); + giveusage = 1; + } + break; + case 'r': + st_flag = DBM_REPLACE; + break; + case 's': + what = STORE; + break; + case 't': + flags |= O_TRUNC; + break; + case 'v': + verbose = 1; + break; + case 'x': + flags |= O_EXCL; + break; + case '!': + giveusage = 1; + break; + case '?': + if (argn < 3) + comarg[argn++] = optarg; + else { + fprintf(stderr, "Too many arguments.\n"); + giveusage = 1; + } + break; + } + } + + if (giveusage | what == YOW | argn < 1) { + fprintf(stderr, "Usage: %s databse [-m r|w|rw] [-crtx] -a|-d|-f|-F|-s [key [content]]\n", argv[0]); + exit(-1); + } + + if ((db = dbm_open(comarg[0], flags, 0777)) == NULL) { + fprintf(stderr, "Error opening database \"%s\"\n", comarg[0]); + exit(-1); + } + + if (argn > 1) + key = read_datum(comarg[1]); + if (argn > 2) + content = read_datum(comarg[2]); + + switch (what) { + + case SCAN: + key = dbm_firstkey(db); + if (dbm_error(db)) { + fprintf(stderr, "Error when fetching first key\n"); + goto db_exit; + } + while (key.dptr != NULL) { + content = dbm_fetch(db, key); + if (dbm_error(db)) { + fprintf(stderr, "Error when fetching "); + print_datum(key); + printf("\n"); + goto db_exit; + } + print_datum(key); + printf(": "); + print_datum(content); + printf("\n"); + if (dbm_error(db)) { + fprintf(stderr, "Error when fetching next key\n"); + goto db_exit; + } + key = dbm_nextkey(db); + } + break; + + case REGEXP: + if (argn < 2) { + fprintf(stderr, "Missing regular expression.\n"); + goto db_exit; + } + if (re_comp(comarg[1])) { + fprintf(stderr, "Invalid regular expression\n"); + goto db_exit; + } + key = dbm_firstkey(db); + if (dbm_error(db)) { + fprintf(stderr, "Error when fetching first key\n"); + goto db_exit; + } + while (key.dptr != NULL) { + if (re_exec(key2s(key))) { + content = dbm_fetch(db, key); + if (dbm_error(db)) { + fprintf(stderr, "Error when fetching "); + print_datum(key); + printf("\n"); + goto db_exit; + } + print_datum(key); + printf(": "); + print_datum(content); + printf("\n"); + if (dbm_error(db)) { + fprintf(stderr, "Error when fetching next key\n"); + goto db_exit; + } + } + key = dbm_nextkey(db); + } + break; + + case FETCH: + if (argn < 2) { + fprintf(stderr, "Missing fetch key.\n"); + goto db_exit; + } + content = dbm_fetch(db, key); + if (dbm_error(db)) { + fprintf(stderr, "Error when fetching "); + print_datum(key); + printf("\n"); + goto db_exit; + } + if (content.dptr == NULL) { + fprintf(stderr, "Cannot find "); + print_datum(key); + printf("\n"); + goto db_exit; + } + print_datum(key); + printf(": "); + print_datum(content); + printf("\n"); + break; + + case DELETE: + if (argn < 2) { + fprintf(stderr, "Missing delete key.\n"); + goto db_exit; + } + if (dbm_delete(db, key) || dbm_error(db)) { + fprintf(stderr, "Error when deleting "); + print_datum(key); + printf("\n"); + goto db_exit; + } + if (verbose) { + print_datum(key); + printf(": DELETED\n"); + } + break; + + case STORE: + if (argn < 3) { + fprintf(stderr, "Missing key and/or content.\n"); + goto db_exit; + } + if (dbm_store(db, key, content, st_flag) || dbm_error(db)) { + fprintf(stderr, "Error when storing "); + print_datum(key); + printf("\n"); + goto db_exit; + } + if (verbose) { + print_datum(key); + printf(": "); + print_datum(content); + printf(" STORED\n"); + } + break; + } + +db_exit: + dbm_clearerr(db); + dbm_close(db); + if (dbm_error(db)) { + fprintf(stderr, "Error closing database \"%s\"\n", comarg[0]); + exit(-1); + } +} diff --git a/ext/SDBM_File/sdbm/dbm.c b/ext/SDBM_File/sdbm/dbm.c new file mode 100644 index 0000000000..1388230e2d --- /dev/null +++ b/ext/SDBM_File/sdbm/dbm.c @@ -0,0 +1,120 @@ +/* + * Copyright (c) 1985 The Regents of the University of California. + * All rights reserved. + * + * Redistribution and use in source and binary forms are permitted + * provided that the above copyright notice and this paragraph are + * duplicated in all such forms and that any documentation, + * advertising materials, and other materials related to such + * distribution and use acknowledge that the software was developed + * by the University of California, Berkeley. The name of the + * University may not be used to endorse or promote products derived + * from this software without specific prior written permission. + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. + */ + +#ifndef lint +static char sccsid[] = "@(#)dbm.c 5.4 (Berkeley) 5/24/89"; +#endif /* not lint */ + +#include "dbm.h" + +#define NODB ((DBM *)0) + +static DBM *cur_db = NODB; + +static char no_db[] = "dbm: no open database\n"; + +dbminit(file) + char *file; +{ + if (cur_db != NODB) + dbm_close(cur_db); + + cur_db = dbm_open(file, 2, 0); + if (cur_db == NODB) { + cur_db = dbm_open(file, 0, 0); + if (cur_db == NODB) + return (-1); + } + return (0); +} + +long +forder(key) +datum key; +{ + if (cur_db == NODB) { + printf(no_db); + return (0L); + } + return (dbm_forder(cur_db, key)); +} + +datum +fetch(key) +datum key; +{ + datum item; + + if (cur_db == NODB) { + printf(no_db); + item.dptr = 0; + return (item); + } + return (dbm_fetch(cur_db, key)); +} + +delete(key) +datum key; +{ + if (cur_db == NODB) { + printf(no_db); + return (-1); + } + if (dbm_rdonly(cur_db)) + return (-1); + return (dbm_delete(cur_db, key)); +} + +store(key, dat) +datum key, dat; +{ + if (cur_db == NODB) { + printf(no_db); + return (-1); + } + if (dbm_rdonly(cur_db)) + return (-1); + + return (dbm_store(cur_db, key, dat, DBM_REPLACE)); +} + +datum +firstkey() +{ + datum item; + + if (cur_db == NODB) { + printf(no_db); + item.dptr = 0; + return (item); + } + return (dbm_firstkey(cur_db)); +} + +datum +nextkey(key) +datum key; +{ + datum item; + + if (cur_db == NODB) { + printf(no_db); + item.dptr = 0; + return (item); + } + return (dbm_nextkey(cur_db, key)); +} diff --git a/ext/SDBM_File/sdbm/dbm.h b/ext/SDBM_File/sdbm/dbm.h new file mode 100644 index 0000000000..1196953d96 --- /dev/null +++ b/ext/SDBM_File/sdbm/dbm.h @@ -0,0 +1,35 @@ +/* + * Copyright (c) 1983 The Regents of the University of California. + * All rights reserved. + * + * Redistribution and use in source and binary forms are permitted + * provided that the above copyright notice and this paragraph are + * duplicated in all such forms and that any documentation, + * advertising materials, and other materials related to such + * distribution and use acknowledge that the software was developed + * by the University of California, Berkeley. The name of the + * University may not be used to endorse or promote products derived + * from this software without specific prior written permission. + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. + * + * @(#)dbm.h 5.2 (Berkeley) 5/24/89 + */ + +#ifndef NULL +/* + * this is lunacy, we no longer use it (and never should have + * unconditionally defined it), but, this whole file is for + * backwards compatability - someone may rely on this. + */ +#define NULL ((char *) 0) +#endif + +#ifdef I_NDBM +# include <ndbm.h> +#endif + +datum fetch(); +datum firstkey(); +datum nextkey(); diff --git a/ext/SDBM_File/sdbm/dbu.c b/ext/SDBM_File/sdbm/dbu.c new file mode 100644 index 0000000000..106262872e --- /dev/null +++ b/ext/SDBM_File/sdbm/dbu.c @@ -0,0 +1,250 @@ +#include <stdio.h> +#include <sys/file.h> +#ifdef SDBM +#include "sdbm.h" +#else +#include <ndbm.h> +#endif +#include <string.h> + +#ifdef BSD42 +#define strchr index +#endif + +extern int getopt(); +extern char *strchr(); +extern void oops(); + +char *progname; + +static int rflag; +static char *usage = "%s [-R] cat | look |... dbmname"; + +#define DERROR 0 +#define DLOOK 1 +#define DINSERT 2 +#define DDELETE 3 +#define DCAT 4 +#define DBUILD 5 +#define DPRESS 6 +#define DCREAT 7 + +#define LINEMAX 8192 + +typedef struct { + char *sname; + int scode; + int flags; +} cmd; + +static cmd cmds[] = { + + "fetch", DLOOK, O_RDONLY, + "get", DLOOK, O_RDONLY, + "look", DLOOK, O_RDONLY, + "add", DINSERT, O_RDWR, + "insert", DINSERT, O_RDWR, + "store", DINSERT, O_RDWR, + "delete", DDELETE, O_RDWR, + "remove", DDELETE, O_RDWR, + "dump", DCAT, O_RDONLY, + "list", DCAT, O_RDONLY, + "cat", DCAT, O_RDONLY, + "creat", DCREAT, O_RDWR | O_CREAT | O_TRUNC, + "new", DCREAT, O_RDWR | O_CREAT | O_TRUNC, + "build", DBUILD, O_RDWR | O_CREAT, + "squash", DPRESS, O_RDWR, + "compact", DPRESS, O_RDWR, + "compress", DPRESS, O_RDWR +}; + +#define CTABSIZ (sizeof (cmds)/sizeof (cmd)) + +static cmd *parse(); +static void badk(), doit(), prdatum(); + +int +main(argc, argv) +int argc; +char *argv[]; +{ + int c; + register cmd *act; + extern int optind; + extern char *optarg; + + progname = argv[0]; + + while ((c = getopt(argc, argv, "R")) != EOF) + switch (c) { + case 'R': /* raw processing */ + rflag++; + break; + + default: + oops("usage: %s", usage); + break; + } + + if ((argc -= optind) < 2) + oops("usage: %s", usage); + + if ((act = parse(argv[optind])) == NULL) + badk(argv[optind]); + optind++; + doit(act, argv[optind]); + return 0; +} + +static void +doit(act, file) +register cmd *act; +char *file; +{ + datum key; + datum val; + register DBM *db; + register char *op; + register int n; + char *line; +#ifdef TIME + long start; + extern long time(); +#endif + + if ((db = dbm_open(file, act->flags, 0644)) == NULL) + oops("cannot open: %s", file); + + if ((line = (char *) malloc(LINEMAX)) == NULL) + oops("%s: cannot get memory", "line alloc"); + + switch (act->scode) { + + case DLOOK: + while (fgets(line, LINEMAX, stdin) != NULL) { + n = strlen(line) - 1; + line[n] = 0; + key.dptr = line; + key.dsize = n; + val = dbm_fetch(db, key); + if (val.dptr != NULL) { + prdatum(stdout, val); + putchar('\n'); + continue; + } + prdatum(stderr, key); + fprintf(stderr, ": not found.\n"); + } + break; + case DINSERT: + break; + case DDELETE: + while (fgets(line, LINEMAX, stdin) != NULL) { + n = strlen(line) - 1; + line[n] = 0; + key.dptr = line; + key.dsize = n; + if (dbm_delete(db, key) == -1) { + prdatum(stderr, key); + fprintf(stderr, ": not found.\n"); + } + } + break; + case DCAT: + for (key = dbm_firstkey(db); key.dptr != 0; + key = dbm_nextkey(db)) { + prdatum(stdout, key); + putchar('\t'); + prdatum(stdout, dbm_fetch(db, key)); + putchar('\n'); + } + break; + case DBUILD: +#ifdef TIME + start = time(0); +#endif + while (fgets(line, LINEMAX, stdin) != NULL) { + n = strlen(line) - 1; + line[n] = 0; + key.dptr = line; + if ((op = strchr(line, '\t')) != 0) { + key.dsize = op - line; + *op++ = 0; + val.dptr = op; + val.dsize = line + n - op; + } + else + oops("bad input; %s", line); + + if (dbm_store(db, key, val, DBM_REPLACE) < 0) { + prdatum(stderr, key); + fprintf(stderr, ": "); + oops("store: %s", "failed"); + } + } +#ifdef TIME + printf("done: %d seconds.\n", time(0) - start); +#endif + break; + case DPRESS: + break; + case DCREAT: + break; + } + + dbm_close(db); +} + +static void +badk(word) +char *word; +{ + register int i; + + if (progname) + fprintf(stderr, "%s: ", progname); + fprintf(stderr, "bad keywd %s. use one of\n", word); + for (i = 0; i < (int)CTABSIZ; i++) + fprintf(stderr, "%-8s%c", cmds[i].sname, + ((i + 1) % 6 == 0) ? '\n' : ' '); + fprintf(stderr, "\n"); + exit(1); + /*NOTREACHED*/ +} + +static cmd * +parse(str) +register char *str; +{ + register int i = CTABSIZ; + register cmd *p; + + for (p = cmds; i--; p++) + if (strcmp(p->sname, str) == 0) + return p; + return NULL; +} + +static void +prdatum(stream, d) +FILE *stream; +datum d; +{ + register int c; + register char *p = d.dptr; + register int n = d.dsize; + + while (n--) { + c = *p++ & 0377; + if (c & 0200) { + fprintf(stream, "M-"); + c &= 0177; + } + if (c == 0177 || c < ' ') + fprintf(stream, "^%c", (c == 0177) ? '?' : c + '@'); + else + putc(c, stream); + } +} + + diff --git a/ext/SDBM_File/sdbm/grind b/ext/SDBM_File/sdbm/grind new file mode 100755 index 0000000000..23728b7d49 --- /dev/null +++ b/ext/SDBM_File/sdbm/grind @@ -0,0 +1,9 @@ +#!/bin/sh +rm -f /tmp/*.dir /tmp/*.pag +awk -e '{ + printf "%s\t", $0 + for (i = 0; i < 40; i++) + printf "%s.", $0 + printf "\n" +}' < /usr/dict/words | $1 build /tmp/$2 + diff --git a/ext/SDBM_File/sdbm/hash.c b/ext/SDBM_File/sdbm/hash.c new file mode 100644 index 0000000000..eb585ac102 --- /dev/null +++ b/ext/SDBM_File/sdbm/hash.c @@ -0,0 +1,48 @@ +/* + * sdbm - ndbm work-alike hashed database library + * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). + * author: oz@nexus.yorku.ca + * status: public domain. keep it that way. + * + * hashing routine + */ + +#include "config.h" +#include "sdbm.h" +/* + * polynomial conversion ignoring overflows + * [this seems to work remarkably well, in fact better + * then the ndbm hash function. Replace at your own risk] + * use: 65599 nice. + * 65587 even better. + */ +long +sdbm_hash(str, len) +register char *str; +register int len; +{ + register unsigned long n = 0; + +#ifdef DUFF + +#define HASHC n = *str++ + 65599 * n + + if (len > 0) { + register int loop = (len + 8 - 1) >> 3; + + switch(len & (8 - 1)) { + case 0: do { + HASHC; case 7: HASHC; + case 6: HASHC; case 5: HASHC; + case 4: HASHC; case 3: HASHC; + case 2: HASHC; case 1: HASHC; + } while (--loop); + } + + } +#else + while (len--) + n = *str++ + 65599 * n; +#endif + return n; +} diff --git a/ext/SDBM_File/sdbm/linux.patches b/ext/SDBM_File/sdbm/linux.patches new file mode 100644 index 0000000000..cb7b1b7d8e --- /dev/null +++ b/ext/SDBM_File/sdbm/linux.patches @@ -0,0 +1,67 @@ +*** sdbm.dist/./dbu.c Mon Feb 17 21:18:52 1992 +--- sdbm/./dbu.c Mon Feb 17 21:11:20 1992 +*************** +*** 12,18 **** + #endif + + extern int getopt(); +! extern char *strchr(); + extern void oops(); + + char *progname; +--- 12,18 ---- + #endif + + extern int getopt(); +! /* extern char *strchr(); */ + extern void oops(); + + char *progname; +*** sdbm.dist/./makefile Mon Feb 17 21:18:56 1992 +--- sdbm/./makefile Mon Feb 17 21:10:46 1992 +*************** +*** 2,8 **** + # makefile for public domain ndbm-clone: sdbm + # DUFF: use duff's device (loop unroll) in parts of the code + # +! CFLAGS = -O -DSDBM -DDUFF -DBSD42 + #LDFLAGS = -p + + OBJS = sdbm.o pair.o hash.o +--- 2,8 ---- + # makefile for public domain ndbm-clone: sdbm + # DUFF: use duff's device (loop unroll) in parts of the code + # +! CFLAGS = -O -DSDBM -DDUFF + #LDFLAGS = -p + + OBJS = sdbm.o pair.o hash.o +*** sdbm.dist/./sdbm.c Mon Feb 17 21:19:17 1992 +--- sdbm/./sdbm.c Mon Feb 17 21:12:59 1992 +*************** +*** 25,30 **** +--- 25,31 ---- + #endif + #include <errno.h> + #include <string.h> ++ #include <unistd.h> + + #ifdef __STDC__ + #include <stddef.h> +*************** +*** 43,49 **** + + extern char *malloc proto((unsigned int)); + extern void free proto((void *)); +! extern long lseek(); + + /* + * forward +--- 44,50 ---- + + extern char *malloc proto((unsigned int)); + extern void free proto((void *)); +! /* extern long lseek(); */ + + /* + * forward diff --git a/ext/SDBM_File/sdbm/makefile.sdbm b/ext/SDBM_File/sdbm/makefile.sdbm new file mode 100644 index 0000000000..c959c1fab5 --- /dev/null +++ b/ext/SDBM_File/sdbm/makefile.sdbm @@ -0,0 +1,55 @@ +# +# makefile for public domain ndbm-clone: sdbm +# DUFF: use duff's device (loop unroll) in parts of the code +# +CFLAGS = -O -DSDBM -DDUFF -DBSD42 -pic +#LDFLAGS = -p + +OBJS = sdbm.o pair.o hash.o +SRCS = sdbm.c pair.c hash.c dbu.c dba.c dbd.c util.c +HDRS = tune.h sdbm.h pair.h +MISC = README CHANGES COMPARE sdbm.3 dbe.c dbe.1 dbm.c dbm.h biblio \ + readme.ms readme.ps + +all: dbu dba dbd dbe + +dbu: dbu.o sdbm util.o + cc $(LDFLAGS) -o dbu dbu.o util.o libsdbm.a + +dba: dba.o util.o + cc $(LDFLAGS) -o dba dba.o util.o +dbd: dbd.o util.o + cc $(LDFLAGS) -o dbd dbd.o util.o +dbe: dbe.o sdbm + cc $(LDFLAGS) -o dbe dbe.o libsdbm.a + +sdbm: $(OBJS) + ar cr libsdbm.a $(OBJS) + ranlib libsdbm.a +### cp libsdbm.a /usr/lib/libsdbm.a + +dba.o: sdbm.h +dbu.o: sdbm.h +util.o:sdbm.h + +$(OBJS): sdbm.h tune.h pair.h + +# +# dbu using berkelezoid ndbm routines [if you have them] for testing +# +#x-dbu: dbu.o util.o +# cc $(CFLAGS) -o x-dbu dbu.o util.o +lint: + lint -abchx $(SRCS) + +clean: + rm -f *.o mon.out core + +purge: clean + rm -f dbu libsdbm.a dbd dba dbe x-dbu *.dir *.pag + +shar: + shar $(MISC) makefile $(SRCS) $(HDRS) >SDBM.SHAR + +readme: + nroff -ms readme.ms | col -b >README diff --git a/ext/SDBM_File/sdbm/pair.c b/ext/SDBM_File/sdbm/pair.c new file mode 100644 index 0000000000..a02c73f28f --- /dev/null +++ b/ext/SDBM_File/sdbm/pair.c @@ -0,0 +1,307 @@ +/* + * sdbm - ndbm work-alike hashed database library + * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). + * author: oz@nexus.yorku.ca + * status: public domain. + * + * page-level routines + */ + +#ifndef lint +static char rcsid[] = "$Id: pair.c,v 1.10 90/12/13 13:00:35 oz Exp $"; +#endif + +#include "config.h" +#include "sdbm.h" +#include "tune.h" +#include "pair.h" + +#define exhash(item) sdbm_hash((item).dptr, (item).dsize) + +/* + * forward + */ +static int seepair proto((char *, int, char *, int)); + +/* + * page format: + * +------------------------------+ + * ino | n | keyoff | datoff | keyoff | + * +------------+--------+--------+ + * | datoff | - - - ----> | + * +--------+---------------------+ + * | F R E E A R E A | + * +--------------+---------------+ + * | <---- - - - | data | + * +--------+-----+----+----------+ + * | key | data | key | + * +--------+----------+----------+ + * + * calculating the offsets for free area: if the number + * of entries (ino[0]) is zero, the offset to the END of + * the free area is the block size. Otherwise, it is the + * nth (ino[ino[0]]) entry's offset. + */ + +int +fitpair(pag, need) +char *pag; +int need; +{ + register int n; + register int off; + register int free; + register short *ino = (short *) pag; + + off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; + free = off - (n + 1) * sizeof(short); + need += 2 * sizeof(short); + + debug(("free %d need %d\n", free, need)); + + return need <= free; +} + +void +putpair(pag, key, val) +char *pag; +datum key; +datum val; +{ + register int n; + register int off; + register short *ino = (short *) pag; + + off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ; +/* + * enter the key first + */ + off -= key.dsize; + (void) memcpy(pag + off, key.dptr, key.dsize); + ino[n + 1] = off; +/* + * now the data + */ + off -= val.dsize; + (void) memcpy(pag + off, val.dptr, val.dsize); + ino[n + 2] = off; +/* + * adjust item count + */ + ino[0] += 2; +} + +datum +getpair(pag, key) +char *pag; +datum key; +{ + register int i; + register int n; + datum val; + register short *ino = (short *) pag; + + if ((n = ino[0]) == 0) + return nullitem; + + if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) + return nullitem; + + val.dptr = pag + ino[i + 1]; + val.dsize = ino[i] - ino[i + 1]; + return val; +} + +#ifdef SEEDUPS +int +duppair(pag, key) +char *pag; +datum key; +{ + register short *ino = (short *) pag; + return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0; +} +#endif + +datum +getnkey(pag, num) +char *pag; +int num; +{ + datum key; + register int off; + register short *ino = (short *) pag; + + num = num * 2 - 1; + if (ino[0] == 0 || num > ino[0]) + return nullitem; + + off = (num > 1) ? ino[num - 1] : PBLKSIZ; + + key.dptr = pag + ino[num]; + key.dsize = off - ino[num]; + + return key; +} + +int +delpair(pag, key) +char *pag; +datum key; +{ + register int n; + register int i; + register short *ino = (short *) pag; + + if ((n = ino[0]) == 0) + return 0; + + if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0) + return 0; +/* + * found the key. if it is the last entry + * [i.e. i == n - 1] we just adjust the entry count. + * hard case: move all data down onto the deleted pair, + * shift offsets onto deleted offsets, and adjust them. + * [note: 0 < i < n] + */ + if (i < n - 1) { + register int m; + register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]); + register char *src = pag + ino[i + 1]; + register int zoo = dst - src; + + debug(("free-up %d ", zoo)); +/* + * shift data/keys down + */ + m = ino[i + 1] - ino[n]; +#ifdef DUFF +#define MOVB *--dst = *--src + + if (m > 0) { + register int loop = (m + 8 - 1) >> 3; + + switch (m & (8 - 1)) { + case 0: do { + MOVB; case 7: MOVB; + case 6: MOVB; case 5: MOVB; + case 4: MOVB; case 3: MOVB; + case 2: MOVB; case 1: MOVB; + } while (--loop); + } + } +#else +#ifdef HAS_MEMMOVE + dst -= m; + src -= m; + memmove(dst, src, m); +#else + while (m--) + *--dst = *--src; +#endif +#endif +/* + * adjust offset index up + */ + while (i < n - 1) { + ino[i] = ino[i + 2] + zoo; + i++; + } + } + ino[0] -= 2; + return 1; +} + +/* + * search for the key in the page. + * return offset index in the range 0 < i < n. + * return 0 if not found. + */ +static int +seepair(pag, n, key, siz) +char *pag; +register int n; +register char *key; +register int siz; +{ + register int i; + register int off = PBLKSIZ; + register short *ino = (short *) pag; + + for (i = 1; i < n; i += 2) { + if (siz == off - ino[i] && + memcmp(key, pag + ino[i], siz) == 0) + return i; + off = ino[i + 1]; + } + return 0; +} + +void +splpage(pag, new, sbit) +char *pag; +char *new; +long sbit; +{ + datum key; + datum val; + + register int n; + register int off = PBLKSIZ; + char cur[PBLKSIZ]; + register short *ino = (short *) cur; + + (void) memcpy(cur, pag, PBLKSIZ); + (void) memset(pag, 0, PBLKSIZ); + (void) memset(new, 0, PBLKSIZ); + + n = ino[0]; + for (ino++; n > 0; ino += 2) { + key.dptr = cur + ino[0]; + key.dsize = off - ino[0]; + val.dptr = cur + ino[1]; + val.dsize = ino[0] - ino[1]; +/* + * select the page pointer (by looking at sbit) and insert + */ + (void) putpair((exhash(key) & sbit) ? new : pag, key, val); + + off = ino[1]; + n -= 2; + } + + debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, + ((short *) new)[0] / 2, + ((short *) pag)[0] / 2)); +} + +/* + * check page sanity: + * number of entries should be something + * reasonable, and all offsets in the index should be in order. + * this could be made more rigorous. + */ +int +chkpage(pag) +char *pag; +{ + register int n; + register int off; + register short *ino = (short *) pag; + + if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short)) + return 0; + + if (n > 0) { + off = PBLKSIZ; + for (ino++; n > 0; ino += 2) { + if (ino[0] > off || ino[1] > off || + ino[1] > ino[0]) + return 0; + off = ino[1]; + n -= 2; + } + } + return 1; +} diff --git a/ext/SDBM_File/sdbm/pair.h b/ext/SDBM_File/sdbm/pair.h new file mode 100644 index 0000000000..bd66d02fd2 --- /dev/null +++ b/ext/SDBM_File/sdbm/pair.h @@ -0,0 +1,10 @@ +extern int fitpair proto((char *, int)); +extern void putpair proto((char *, datum, datum)); +extern datum getpair proto((char *, datum)); +extern int delpair proto((char *, datum)); +extern int chkpage proto((char *)); +extern datum getnkey proto((char *, int)); +extern void splpage proto((char *, char *, long)); +#ifdef SEEDUPS +extern int duppair proto((char *, datum)); +#endif diff --git a/ext/SDBM_File/sdbm/readme.ms b/ext/SDBM_File/sdbm/readme.ms new file mode 100644 index 0000000000..01ca17ccdf --- /dev/null +++ b/ext/SDBM_File/sdbm/readme.ms @@ -0,0 +1,353 @@ +.\" tbl | readme.ms | [tn]roff -ms | ... +.\" note the "C" (courier) and "CB" fonts: you will probably have to +.\" change these. +.\" $Id: readme.ms,v 1.1 90/12/13 13:09:15 oz Exp Locker: oz $ + +.de P1 +.br +.nr dT 4 +.nf +.ft C +.sp .5 +.nr t \\n(dT*\\w'x'u +.ta 1u*\\ntu 2u*\\ntu 3u*\\ntu 4u*\\ntu 5u*\\ntu 6u*\\ntu 7u*\\ntu 8u*\\ntu 9u*\\ntu 10u*\\ntu 11u*\\ntu 12u*\\ntu 13u*\\ntu 14u*\\ntu +.. +.de P2 +.br +.ft 1 +.br +.sp .5 +.br +.fi +.. +.\" CW uses the typewriter/courier font. +.de CW +\fC\\$1\\fP\\$2 +.. + +.\" Footnote numbering [by Henry Spencer] +.\" <text>\*f for a footnote number.. +.\" .FS +.\" \*F <footnote text> +.\" .FE +.\" +.ds f \\u\\s-2\\n+f\\s+2\\d +.nr f 0 1 +.ds F \\n+F. +.nr F 0 1 + +.ND +.LP +.TL +\fIsdbm\fP \(em Substitute DBM +.br +or +.br +Berkeley \fIndbm\fP for Every UN*X\** Made Simple +.AU +Ozan (oz) Yigit +.AI +The Guild of PD Software Toolmakers +Toronto - Canada +.sp +oz@nexus.yorku.ca +.LP +.FS +UN*X is not a trademark of any (dis)organization. +.FE +.sp 2 +\fIImplementation is the sincerest form of flattery. \(em L. Peter Deutsch\fP +.SH +A The Clone of the \fIndbm\fP library +.PP +The sources accompanying this notice \(em \fIsdbm\fP \(em constitute +the first public release (Dec. 1990) of a complete clone of +the Berkeley UN*X \fIndbm\fP library. The \fIsdbm\fP library is meant to +clone the proven functionality of \fIndbm\fP as closely as possible, +including a few improvements. It is practical, easy to understand, and +compatible. +The \fIsdbm\fP library is not derived from any licensed, proprietary or +copyrighted software. +.PP +The \fIsdbm\fP implementation is based on a 1978 algorithm +[Lar78] by P.-A. (Paul) Larson known as ``Dynamic Hashing''. +In the course of searching for a substitute for \fIndbm\fP, I +prototyped three different external-hashing algorithms [Lar78, Fag79, Lit80] +and ultimately chose Larson's algorithm as a basis of the \fIsdbm\fP +implementation. The Bell Labs +\fIdbm\fP (and therefore \fIndbm\fP) is based on an algorithm invented by +Ken Thompson, [Tho90, Tor87] and predates Larson's work. +.PP +The \fIsdbm\fR programming interface is totally compatible +with \fIndbm\fP and includes a slight improvement in database initialization. +It is also expected to be binary-compatible under most UN*X versions that +support the \fIndbm\fP library. +.PP +The \fIsdbm\fP implementation shares the shortcomings of the \fIndbm\fP +library, as a side effect of various simplifications to the original Larson +algorithm. It does produce \fIholes\fP in the page file as it writes +pages past the end of file. (Larson's paper include a clever solution to +this problem that is a result of using the hash value directly as a block +address.) On the other hand, extensive tests seem to indicate that \fIsdbm\fP +creates fewer holes in general, and the resulting pagefiles are +smaller. The \fIsdbm\fP implementation is also faster than \fIndbm\fP +in database creation. +Unlike the \fIndbm\fP, the \fIsdbm\fP +.CW store +operation will not ``wander away'' trying to split its +data pages to insert a datum that \fIcannot\fP (due to elaborate worst-case +situations) be inserted. (It will fail after a pre-defined number of attempts.) +.SH +Important Compatibility Warning +.PP +The \fIsdbm\fP and \fIndbm\fP +libraries \fIcannot\fP share databases: one cannot read the (dir/pag) +database created by the other. This is due to the differences +between the \fIndbm\fP and \fIsdbm\fP algorithms\**, +.FS +Torek's discussion [Tor87] +indicates that \fIdbm/ndbm\fP implementations use the hash +value to traverse the radix trie differently than \fIsdbm\fP +and as a result, the page indexes are generated in \fIdifferent\fP order. +For more information, send e-mail to the author. +.FE +and the hash functions +used. +It is easy to convert between the \fIdbm/ndbm\fP databases and \fIsdbm\fP +by ignoring the index completely: see +.CW dbd , +.CW dbu +etc. +.R +.LP +.SH +Notice of Intellectual Property +.LP +\fIThe entire\fP sdbm \fIlibrary package, as authored by me,\fP Ozan S. Yigit, +\fIis hereby placed in the public domain.\fP As such, the author is not +responsible for the consequences of use of this software, no matter how +awful, even if they arise from defects in it. There is no expressed or +implied warranty for the \fIsdbm\fP library. +.PP +Since the \fIsdbm\fP +library package is in the public domain, this \fIoriginal\fP +release or any additional public-domain releases of the modified original +cannot possibly (by definition) be withheld from you. Also by definition, +You (singular) have all the rights to this code (including the right to +sell without permission, the right to hoard\** +.FS +You cannot really hoard something that is available to the public at +large, but try if it makes you feel any better. +.FE +and the right to do other icky things as +you see fit) but those rights are also granted to everyone else. +.PP +Please note that all previous distributions of this software contained +a copyright (which is now dropped) to protect its +origins and its current public domain status against any possible claims +and/or challenges. +.SH +Acknowledgments +.PP +Many people have been very helpful and supportive. A partial list would +necessarily include Rayan Zacherissen (who contributed the man page, +and also hacked a MMAP version of \fIsdbm\fP), +Arnold Robbins, Chris Lewis, +Bill Davidsen, Henry Spencer, Geoff Collyer, Rich Salz (who got me started +in the first place), Johannes Ruschein +(who did the minix port) and David Tilbrook. I thank you all. +.SH +Distribution Manifest and Notes +.LP +This distribution of \fIsdbm\fP includes (at least) the following: +.P1 + CHANGES change log + README this file. + biblio a small bibliography on external hashing + dba.c a crude (n/s)dbm page file analyzer + dbd.c a crude (n/s)dbm page file dumper (for conversion) + dbe.1 man page for dbe.c + dbe.c Janick's database editor + dbm.c a dbm library emulation wrapper for ndbm/sdbm + dbm.h header file for the above + dbu.c a crude db management utility + hash.c hashing function + makefile guess. + pair.c page-level routines (posted earlier) + pair.h header file for the above + readme.ms troff source for the README file + sdbm.3 man page + sdbm.c the real thing + sdbm.h header file for the above + tune.h place for tuning & portability thingies + util.c miscellaneous +.P2 +.PP +.CW dbu +is a simple database manipulation program\** that tries to look +.FS +The +.CW dbd , +.CW dba , +.CW dbu +utilities are quick hacks and are not fit for production use. They were +developed late one night, just to test out \fIsdbm\fP, and convert some +databases. +.FE +like Bell Labs' +.CW cbt +utility. It is currently incomplete in functionality. +I use +.CW dbu +to test out the routines: it takes (from stdin) tab separated +key/value pairs for commands like +.CW build +or +.CW insert +or takes keys for +commands like +.CW delete +or +.CW look . +.P1 + dbu <build|creat|look|insert|cat|delete> dbmfile +.P2 +.PP +.CW dba +is a crude analyzer of \fIdbm/sdbm/ndbm\fP +page files. It scans the entire +page file, reporting page level statistics, and totals at the end. +.PP +.CW dbd +is a crude dump program for \fIdbm/ndbm/sdbm\fP +databases. It ignores the +bitmap, and dumps the data pages in sequence. It can be used to create +input for the +.CW dbu +utility. +Note that +.CW dbd +will skip any NULLs in the key and data +fields, thus is unsuitable to convert some peculiar databases that +insist in including the terminating null. +.PP +I have also included a copy of the +.CW dbe +(\fIndbm\fP DataBase Editor) by Janick Bergeron [janick@bnr.ca] for +your pleasure. You may find it more useful than the little +.CW dbu +utility. +.PP +.CW dbm.[ch] +is a \fIdbm\fP library emulation on top of \fIndbm\fP +(and hence suitable for \fIsdbm\fP). Written by Robert Elz. +.PP +The \fIsdbm\fP +library has been around in beta test for quite a long time, and from whatever +little feedback I received (maybe no news is good news), I believe it has been +functioning without any significant problems. I would, of course, appreciate +all fixes and/or improvements. Portability enhancements would especially be +useful. +.SH +Implementation Issues +.PP +Hash functions: +The algorithm behind \fIsdbm\fP implementation needs a good bit-scrambling +hash function to be effective. I ran into a set of constants for a simple +hash function that seem to help \fIsdbm\fP perform better than \fIndbm\fP +for various inputs: +.P1 + /* + * polynomial conversion ignoring overflows + * 65599 nice. 65587 even better. + */ + long + dbm_hash(char *str, int len) { + register unsigned long n = 0; + + while (len--) + n = n * 65599 + *str++; + return n; + } +.P2 +.PP +There may be better hash functions for the purposes of dynamic hashing. +Try your favorite, and check the pagefile. If it contains too many pages +with too many holes, (in relation to this one for example) or if +\fIsdbm\fP +simply stops working (fails after +.CW SPLTMAX +attempts to split) when you feed your +NEWS +.CW history +file to it, you probably do not have a good hashing function. +If you do better (for different types of input), I would like to know +about the function you use. +.PP +Block sizes: It seems (from various tests on a few machines) that a page +file block size +.CW PBLKSIZ +of 1024 is by far the best for performance, but +this also happens to limit the size of a key/value pair. Depending on your +needs, you may wish to increase the page size, and also adjust +.CW PAIRMAX +(the maximum size of a key/value pair allowed: should always be at least +three words smaller than +.CW PBLKSIZ .) +accordingly. The system-wide version of the library +should probably be +configured with 1024 (distribution default), as this appears to be sufficient +for most common uses of \fIsdbm\fP. +.SH +Portability +.PP +This package has been tested in many different UN*Xes even including minix, +and appears to be reasonably portable. This does not mean it will port +easily to non-UN*X systems. +.SH +Notes and Miscellaneous +.PP +The \fIsdbm\fP is not a very complicated package, at least not after you +familiarize yourself with the literature on external hashing. There are +other interesting algorithms in existence that ensure (approximately) +single-read access to a data value associated with any key. These are +directory-less schemes such as \fIlinear hashing\fP [Lit80] (+ Larson +variations), \fIspiral storage\fP [Mar79] or directory schemes such as +\fIextensible hashing\fP [Fag79] by Fagin et al. I do hope these sources +provide a reasonable playground for experimentation with other algorithms. +See the June 1988 issue of ACM Computing Surveys [Enb88] for an +excellent overview of the field. +.PG +.SH +References +.LP +.IP [Lar78] 4m +P.-A. Larson, +``Dynamic Hashing'', \fIBIT\fP, vol. 18, pp. 184-201, 1978. +.IP [Tho90] 4m +Ken Thompson, \fIprivate communication\fP, Nov. 1990 +.IP [Lit80] 4m +W. Litwin, +`` Linear Hashing: A new tool for file and table addressing'', +\fIProceedings of the 6th Conference on Very Large Dabatases (Montreal)\fP, +pp. 212-223, Very Large Database Foundation, Saratoga, Calif., 1980. +.IP [Fag79] 4m +R. Fagin, J. Nievergelt, N. Pippinger, and H. R. Strong, +``Extendible Hashing - A Fast Access Method for Dynamic Files'', +\fIACM Trans. Database Syst.\fP, vol. 4, no.3, pp. 315-344, Sept. 1979. +.IP [Wal84] 4m +Rich Wales, +``Discussion of "dbm" data base system'', \fIUSENET newsgroup unix.wizards\fP, +Jan. 1984. +.IP [Tor87] 4m +Chris Torek, +``Re: dbm.a and ndbm.a archives'', \fIUSENET newsgroup comp.unix\fP, +1987. +.IP [Mar79] 4m +G. N. Martin, +``Spiral Storage: Incrementally Augmentable Hash Addressed Storage'', +\fITechnical Report #27\fP, University of Varwick, Coventry, U.K., 1979. +.IP [Enb88] 4m +R. J. Enbody and H. C. Du, +``Dynamic Hashing Schemes'',\fIACM Computing Surveys\fP, +vol. 20, no. 2, pp. 85-113, June 1988. diff --git a/ext/SDBM_File/sdbm/readme.ps b/ext/SDBM_File/sdbm/readme.ps new file mode 100644 index 0000000000..2b0c675595 --- /dev/null +++ b/ext/SDBM_File/sdbm/readme.ps @@ -0,0 +1,2225 @@ +%!PS-Adobe-1.0 +%%Creator: yetti:oz (Ozan Yigit) +%%Title: stdin (ditroff) +%%CreationDate: Thu Dec 13 15:56:08 1990 +%%EndComments +% lib/psdit.pro -- prolog for psdit (ditroff) files +% Copyright (c) 1984, 1985 Adobe Systems Incorporated. All Rights Reserved. +% last edit: shore Sat Nov 23 20:28:03 1985 +% RCSID: $Header: psdit.pro,v 2.1 85/11/24 12:19:43 shore Rel $ + +/$DITroff 140 dict def $DITroff begin +/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def +/xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto + /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F + /pagesave save def}def +/PB{save /psv exch def currentpoint translate + resolution 72 div dup neg scale 0 0 moveto}def +/PE{psv restore}def +/arctoobig 90 def /arctoosmall .05 def +/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def +/tan{dup sin exch cos div}def +/point{resolution 72 div mul}def +/dround {transform round exch round exch itransform}def +/xT{/devname exch def}def +/xr{/mh exch def /my exch def /resolution exch def}def +/xp{}def +/xs{docsave restore end}def +/xt{}def +/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not + {fonts slotno fontname findfont put fontnames slotno fontname put}if}def +/xH{/fontheight exch def F}def +/xS{/fontslant exch def F}def +/s{/fontsize exch def /fontheight fontsize def F}def +/f{/fontnum exch def F}def +/F{fontheight 0 le {/fontheight fontsize def}if + fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore + fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if + makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def +/X{exch currentpoint exch pop moveto show}def +/N{3 1 roll moveto show}def +/Y{exch currentpoint pop exch moveto show}def +/S{show}def +/ditpush{}def/ditpop{}def +/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def +/AN{4 2 roll moveto 0 exch ashow}def +/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def +/AS{0 exch ashow}def +/MX{currentpoint exch pop moveto}def +/MY{currentpoint pop exch moveto}def +/MXY{moveto}def +/cb{pop}def % action on unknown char -- nothing for now +/n{}def/w{}def +/p{pop showpage pagesave restore /pagesave save def}def +/abspoint{currentpoint exch pop add exch currentpoint pop add exch}def +/distance{dup mul exch dup mul add sqrt}def +/dstroke{currentpoint stroke moveto}def +/Dl{2 copy gsave rlineto stroke grestore rmoveto}def +/arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop + currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def + currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def +/Dc{dup arcellipse dstroke}def +/De{arcellipse dstroke}def +/Da{/endv exch def /endh exch def /centerv exch def /centerh exch def + /cradius centerv centerv mul centerh centerh mul add sqrt def + /eradius endv endv mul endh endh mul add sqrt def + /endang endv endh atan def + /startang centerv neg centerh neg atan def + /sweep startang endang sub dup 0 lt{360 add}if def + sweep arctoobig gt + {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def + /midh midang cos midrad mul def /midv midang sin midrad mul def + midh neg midv neg endh endv centerh centerv midh midv Da + currentpoint moveto Da} + {sweep arctoosmall ge + {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def + centerv neg controldelt mul centerh controldelt mul + endv neg controldelt mul centerh add endh add + endh controldelt mul centerv add endv add + centerh endh add centerv endv add rcurveto dstroke} + {centerh endh add centerv endv add rlineto dstroke}ifelse}ifelse}def + +/Barray 200 array def % 200 values in a wiggle +/D~{mark}def +/D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop + /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and + {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def + Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put + Bcontrol Blen 2 sub 2 copy get 2 mul put + Bcontrol Blen 1 sub 2 copy get 2 mul put + /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub + {/i exch def + Bcontrol i get 3 div Bcontrol i 1 add get 3 div + Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div + Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div + /Xbi Xcont Bcontrol i 2 add get 2 div add def + /Ybi Ycont Bcontrol i 3 add get 2 div add def + /Xcont Xcont Bcontrol i 2 add get add def + /Ycont Ycont Bcontrol i 3 add get add def + Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto + }for dstroke}if}def +end +/ditstart{$DITroff begin + /nfonts 60 def % NFONTS makedev/ditroff dependent! + /fonts[nfonts{0}repeat]def + /fontnames[nfonts{()}repeat]def +/docsave save def +}def + +% character outcalls +/oc {/pswid exch def /cc exch def /name exch def + /ditwid pswid fontsize mul resolution mul 72000 div def + /ditsiz fontsize resolution mul 72 div def + ocprocs name known{ocprocs name get exec}{name cb} + ifelse}def +/fractm [.65 0 0 .6 0 0] def +/fraction + {/fden exch def /fnum exch def gsave /cf currentfont def + cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto + fnum show rmoveto currentfont cf setfont(\244)show setfont fden show + grestore ditwid 0 rmoveto} def +/oce {grestore ditwid 0 rmoveto}def +/dm {ditsiz mul}def +/ocprocs 50 dict def ocprocs begin +(14){(1)(4)fraction}def +(12){(1)(2)fraction}def +(34){(3)(4)fraction}def +(13){(1)(3)fraction}def +(23){(2)(3)fraction}def +(18){(1)(8)fraction}def +(38){(3)(8)fraction}def +(58){(5)(8)fraction}def +(78){(7)(8)fraction}def +(sr){gsave 0 .06 dm rmoveto(\326)show oce}def +(is){gsave 0 .15 dm rmoveto(\362)show oce}def +(->){gsave 0 .02 dm rmoveto(\256)show oce}def +(<-){gsave 0 .02 dm rmoveto(\254)show oce}def +(==){gsave 0 .05 dm rmoveto(\272)show oce}def +end + +% an attempt at a PostScript FONT to implement ditroff special chars +% this will enable us to +% cache the little buggers +% generate faster, more compact PS out of psdit +% confuse everyone (including myself)! +50 dict dup begin +/FontType 3 def +/FontName /DIThacks def +/FontMatrix [.001 0 0 .001 0 0] def +/FontBBox [-260 -260 900 900] def% a lie but ... +/Encoding 256 array def +0 1 255{Encoding exch /.notdef put}for +Encoding + dup 8#040/space put %space + dup 8#110/rc put %right ceil + dup 8#111/lt put %left top curl + dup 8#112/bv put %bold vert + dup 8#113/lk put %left mid curl + dup 8#114/lb put %left bot curl + dup 8#115/rt put %right top curl + dup 8#116/rk put %right mid curl + dup 8#117/rb put %right bot curl + dup 8#120/rf put %right floor + dup 8#121/lf put %left floor + dup 8#122/lc put %left ceil + dup 8#140/sq put %square + dup 8#141/bx put %box + dup 8#142/ci put %circle + dup 8#143/br put %box rule + dup 8#144/rn put %root extender + dup 8#145/vr put %vertical rule + dup 8#146/ob put %outline bullet + dup 8#147/bu put %bullet + dup 8#150/ru put %rule + dup 8#151/ul put %underline + pop +/DITfd 100 dict def +/BuildChar{0 begin + /cc exch def /fd exch def + /charname fd /Encoding get cc get def + /charwid fd /Metrics get charname get def + /charproc fd /CharProcs get charname get def + charwid 0 fd /FontBBox get aload pop setcachedevice + 2 setlinejoin 40 setlinewidth + newpath 0 0 moveto gsave charproc grestore + end}def +/BuildChar load 0 DITfd put +%/UniqueID 5 def +/CharProcs 50 dict def +CharProcs begin +/space{}def +/.notdef{}def +/ru{500 0 rls}def +/rn{0 840 moveto 500 0 rls}def +/vr{0 800 moveto 0 -770 rls}def +/bv{0 800 moveto 0 -1000 rls}def +/br{0 750 moveto 0 -1000 rls}def +/ul{0 -140 moveto 500 0 rls}def +/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def +/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def +/sq{80 0 rmoveto currentpoint dround newpath moveto + 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def +/bx{80 0 rmoveto currentpoint dround newpath moveto + 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def +/ci{500 360 rmoveto currentpoint newpath 333 0 360 arc + 50 setlinewidth stroke}def + +/lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def +/lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def +/rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def +/rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def +/lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub + 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def +/rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub + 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def +/lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def +/rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def +/lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def +/rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def +end + +/Metrics 50 dict def Metrics begin +/.notdef 0 def +/space 500 def +/ru 500 def +/br 0 def +/lt 416 def +/lb 416 def +/rt 416 def +/rb 416 def +/lk 416 def +/rk 416 def +/rc 416 def +/lc 416 def +/rf 416 def +/lf 416 def +/bv 416 def +/ob 350 def +/bu 350 def +/ci 750 def +/bx 750 def +/sq 750 def +/rn 500 def +/ul 500 def +/vr 0 def +end + +DITfd begin +/s2 500 def /s4 250 def /s3 333 def +/a4p{arcto pop pop pop pop}def +/2cx{2 copy exch}def +/rls{rlineto stroke}def +/currx{currentpoint pop}def +/dround{transform round exch round exch itransform} def +end +end +/DIThacks exch definefont pop +ditstart +(psc)xT +576 1 1 xr +1(Times-Roman)xf 1 f +2(Times-Italic)xf 2 f +3(Times-Bold)xf 3 f +4(Times-BoldItalic)xf 4 f +5(Helvetica)xf 5 f +6(Helvetica-Bold)xf 6 f +7(Courier)xf 7 f +8(Courier-Bold)xf 8 f +9(Symbol)xf 9 f +10(DIThacks)xf 10 f +10 s +1 f +xi +%%EndProlog + +%%Page: 1 1 +10 s 0 xH 0 xS 1 f +8 s +2 f +12 s +1778 672(sdbm)N +3 f +2004(\320)X +2124(Substitute)X +2563(DBM)X +2237 768(or)N +1331 864(Berkeley)N +2 f +1719(ndbm)X +3 f +1956(for)X +2103(Every)X +2373(UN*X)X +1 f +10 s +2628 832(1)N +3 f +12 s +2692 864(Made)N +2951(Simple)X +2 f +10 s +2041 1056(Ozan)N +2230(\(oz\))X +2375(Yigit)X +1 f +1658 1200(The)N +1803(Guild)X +2005(of)X +2092(PD)X +2214(Software)X +2524(Toolmakers)X +2000 1296(Toronto)N +2278(-)X +2325(Canada)X +1965 1488(oz@nexus.yorku.ca)N +2 f +555 1804(Implementation)N +1078(is)X +1151(the)X +1269(sincerest)X +1574(form)X +1745(of)X +1827(\257attery.)X +2094(\320)X +2185(L.)X +2269(Peter)X +2463(Deutsch)X +3 f +555 1996(A)N +633(The)X +786(Clone)X +1006(of)X +1093(the)X +2 f +1220(ndbm)X +3 f +1418(library)X +1 f +755 2120(The)N +903(sources)X +1167(accompanying)X +1658(this)X +1796(notice)X +2015(\320)X +2 f +2118(sdbm)X +1 f +2309(\320)X +2411(constitute)X +2744(the)X +2864(\256rst)X +3010(public)X +3232(release)X +3478(\(Dec.)X +3677(1990\))X +3886(of)X +3975(a)X +555 2216(complete)N +874(clone)X +1073(of)X +1165(the)X +1288(Berkeley)X +1603(UN*X)X +2 f +1842(ndbm)X +1 f +2045(library.)X +2304(The)X +2 f +2454(sdbm)X +1 f +2648(library)X +2887(is)X +2965(meant)X +3186(to)X +3273(clone)X +3472(the)X +3594(proven)X +3841(func-)X +555 2312(tionality)N +846(of)X +2 f +938(ndbm)X +1 f +1141(as)X +1233(closely)X +1485(as)X +1576(possible,)X +1882(including)X +2208(a)X +2268(few)X +2413(improvements.)X +2915(It)X +2988(is)X +3065(practical,)X +3386(easy)X +3553(to)X +3639(understand,)X +555 2408(and)N +691(compatible.)X +1107(The)X +2 f +1252(sdbm)X +1 f +1441(library)X +1675(is)X +1748(not)X +1870(derived)X +2131(from)X +2307(any)X +2443(licensed,)X +2746(proprietary)X +3123(or)X +3210(copyrighted)X +3613(software.)X +755 2532(The)N +2 f +910(sdbm)X +1 f +1109(implementation)X +1641(is)X +1723(based)X +1935(on)X +2044(a)X +2109(1978)X +2298(algorithm)X +2638([Lar78])X +2913(by)X +3022(P.-A.)X +3220(\(Paul\))X +3445(Larson)X +3697(known)X +3944(as)X +555 2628(``Dynamic)N +934(Hashing''.)X +1326(In)X +1424(the)X +1553(course)X +1794(of)X +1892(searching)X +2231(for)X +2355(a)X +2421(substitute)X +2757(for)X +2 f +2881(ndbm)X +1 f +3059(,)X +3109(I)X +3166(prototyped)X +3543(three)X +3734(different)X +555 2724(external-hashing)N +1119(algorithms)X +1490([Lar78,)X +1758(Fag79,)X +2007(Lit80])X +2236(and)X +2381(ultimately)X +2734(chose)X +2946(Larson's)X +3256(algorithm)X +3596(as)X +3692(a)X +3756(basis)X +3944(of)X +555 2820(the)N +2 f +680(sdbm)X +1 f +875(implementation.)X +1423(The)X +1574(Bell)X +1733(Labs)X +2 f +1915(dbm)X +1 f +2079(\(and)X +2248(therefore)X +2 f +2565(ndbm)X +1 f +2743(\))X +2796(is)X +2875(based)X +3084(on)X +3190(an)X +3292(algorithm)X +3629(invented)X +3931(by)X +555 2916(Ken)N +709(Thompson,)X +1091([Tho90,)X +1367(Tor87])X +1610(and)X +1746(predates)X +2034(Larson's)X +2335(work.)X +755 3040(The)N +2 f +903(sdbm)X +1 f +1095(programming)X +1553(interface)X +1857(is)X +1932(totally)X +2158(compatible)X +2536(with)X +2 f +2700(ndbm)X +1 f +2900(and)X +3038(includes)X +3327(a)X +3385(slight)X +3584(improvement)X +555 3136(in)N +641(database)X +942(initialization.)X +1410(It)X +1483(is)X +1560(also)X +1713(expected)X +2023(to)X +2109(be)X +2208(binary-compatible)X +2819(under)X +3025(most)X +3203(UN*X)X +3440(versions)X +3730(that)X +3873(sup-)X +555 3232(port)N +704(the)X +2 f +822(ndbm)X +1 f +1020(library.)X +755 3356(The)N +2 f +909(sdbm)X +1 f +1107(implementation)X +1638(shares)X +1868(the)X +1995(shortcomings)X +2455(of)X +2551(the)X +2 f +2678(ndbm)X +1 f +2885(library,)X +3148(as)X +3244(a)X +3309(side)X +3467(effect)X +3680(of)X +3775(various)X +555 3452(simpli\256cations)N +1046(to)X +1129(the)X +1248(original)X +1518(Larson)X +1762(algorithm.)X +2114(It)X +2183(does)X +2350(produce)X +2 f +2629(holes)X +1 f +2818(in)X +2900(the)X +3018(page)X +3190(\256le)X +3312(as)X +3399(it)X +3463(writes)X +3679(pages)X +3882(past)X +555 3548(the)N +680(end)X +823(of)X +917(\256le.)X +1066(\(Larson's)X +1400(paper)X +1605(include)X +1867(a)X +1929(clever)X +2152(solution)X +2435(to)X +2523(this)X +2664(problem)X +2957(that)X +3103(is)X +3182(a)X +3244(result)X +3448(of)X +3541(using)X +3740(the)X +3864(hash)X +555 3644(value)N +758(directly)X +1032(as)X +1128(a)X +1193(block)X +1400(address.\))X +1717(On)X +1844(the)X +1971(other)X +2165(hand,)X +2370(extensive)X +2702(tests)X +2873(seem)X +3067(to)X +3158(indicate)X +3441(that)X +2 f +3590(sdbm)X +1 f +3787(creates)X +555 3740(fewer)N +762(holes)X +954(in)X +1039(general,)X +1318(and)X +1456(the)X +1576(resulting)X +1878(page\256les)X +2185(are)X +2306(smaller.)X +2584(The)X +2 f +2731(sdbm)X +1 f +2922(implementation)X +3446(is)X +3521(also)X +3672(faster)X +3873(than)X +2 f +555 3836(ndbm)N +1 f +757(in)X +843(database)X +1144(creation.)X +1467(Unlike)X +1709(the)X +2 f +1831(ndbm)X +1 f +2009(,)X +2053(the)X +2 f +2175(sdbm)X +7 f +2396(store)X +1 f +2660(operation)X +2987(will)X +3134(not)X +3259(``wander)X +3573(away'')X +3820(trying)X +555 3932(to)N +642(split)X +804(its)X +904(data)X +1063(pages)X +1271(to)X +1358(insert)X +1561(a)X +1622(datum)X +1847(that)X +2 f +1992(cannot)X +1 f +2235(\(due)X +2403(to)X +2490(elaborate)X +2810(worst-case)X +3179(situations\))X +3537(be)X +3637(inserted.)X +3935(\(It)X +555 4028(will)N +699(fail)X +826(after)X +994(a)X +1050(pre-de\256ned)X +1436(number)X +1701(of)X +1788(attempts.\))X +3 f +555 4220(Important)N +931(Compatibility)X +1426(Warning)X +1 f +755 4344(The)N +2 f +904(sdbm)X +1 f +1097(and)X +2 f +1237(ndbm)X +1 f +1439(libraries)X +2 f +1726(cannot)X +1 f +1968(share)X +2162(databases:)X +2515(one)X +2654(cannot)X +2891(read)X +3053(the)X +3174(\(dir/pag\))X +3478(database)X +3778(created)X +555 4440(by)N +657(the)X +777(other.)X +984(This)X +1148(is)X +1222(due)X +1359(to)X +1442(the)X +1561(differences)X +1940(between)X +2229(the)X +2 f +2348(ndbm)X +1 f +2547(and)X +2 f +2684(sdbm)X +1 f +2874(algorithms)X +8 s +3216 4415(2)N +10 s +4440(,)Y +3289(and)X +3426(the)X +3545(hash)X +3713(functions)X +555 4536(used.)N +769(It)X +845(is)X +925(easy)X +1094(to)X +1182(convert)X +1449(between)X +1743(the)X +2 f +1867(dbm/ndbm)X +1 f +2231(databases)X +2565(and)X +2 f +2707(sdbm)X +1 f +2902(by)X +3008(ignoring)X +3305(the)X +3429(index)X +3633(completely:)X +555 4632(see)N +7 f +706(dbd)X +1 f +(,)S +7 f +918(dbu)X +1 f +1082(etc.)X +3 f +555 4852(Notice)N +794(of)X +881(Intellectual)X +1288(Property)X +2 f +555 4976(The)N +696(entire)X +1 f +904(sdbm)X +2 f +1118(library)X +1361(package,)X +1670(as)X +1762(authored)X +2072(by)X +2169(me,)X +1 f +2304(Ozan)X +2495(S.)X +2580(Yigit,)X +2 f +2785(is)X +2858(hereby)X +3097(placed)X +3331(in)X +3413(the)X +3531(public)X +3751(domain.)X +1 f +555 5072(As)N +670(such,)X +863(the)X +987(author)X +1218(is)X +1297(not)X +1425(responsible)X +1816(for)X +1936(the)X +2060(consequences)X +2528(of)X +2621(use)X +2754(of)X +2847(this)X +2988(software,)X +3310(no)X +3415(matter)X +3645(how)X +3808(awful,)X +555 5168(even)N +727(if)X +796(they)X +954(arise)X +1126(from)X +1302(defects)X +1550(in)X +1632(it.)X +1716(There)X +1924(is)X +1997(no)X +2097(expressed)X +2434(or)X +2521(implied)X +2785(warranty)X +3091(for)X +3205(the)X +2 f +3323(sdbm)X +1 f +3512(library.)X +8 s +10 f +555 5316(hhhhhhhhhhhhhhhhhh)N +6 s +1 f +635 5391(1)N +8 s +691 5410(UN*X)N +877(is)X +936(not)X +1034(a)X +1078(trademark)X +1352(of)X +1421(any)X +1529(\(dis\)organization.)X +6 s +635 5485(2)N +8 s +691 5504(Torek's)N +908(discussion)X +1194([Tor87])X +1411(indicates)X +1657(that)X +2 f +1772(dbm/ndbm)X +1 f +2061(implementations)X +2506(use)X +2609(the)X +2705(hash)X +2840(value)X +2996(to)X +3064(traverse)X +3283(the)X +3379(radix)X +3528(trie)X +3631(dif-)X +555 5584(ferently)N +772(than)X +2 f +901(sdbm)X +1 f +1055(and)X +1166(as)X +1238(a)X +1285(result,)X +1462(the)X +1559(page)X +1698(indexes)X +1912(are)X +2008(generated)X +2274(in)X +2 f +2343(different)X +1 f +2579(order.)X +2764(For)X +2872(more)X +3021(information,)X +3357(send)X +3492(e-mail)X +3673(to)X +555 5664(the)N +649(author.)X + +2 p +%%Page: 2 2 +8 s 0 xH 0 xS 1 f +10 s +2216 384(-)N +2263(2)X +2323(-)X +755 672(Since)N +971(the)X +2 f +1107(sdbm)X +1 f +1314(library)X +1566(package)X +1868(is)X +1959(in)X +2058(the)X +2193(public)X +2430(domain,)X +2727(this)X +2 f +2879(original)X +1 f +3173(release)X +3434(or)X +3538(any)X +3691(additional)X +555 768(public-domain)N +1045(releases)X +1323(of)X +1413(the)X +1534(modi\256ed)X +1841(original)X +2112(cannot)X +2348(possibly)X +2636(\(by)X +2765(de\256nition\))X +3120(be)X +3218(withheld)X +3520(from)X +3698(you.)X +3860(Also)X +555 864(by)N +659(de\256nition,)X +1009(You)X +1170(\(singular\))X +1505(have)X +1680(all)X +1783(the)X +1904(rights)X +2109(to)X +2194(this)X +2332(code)X +2507(\(including)X +2859(the)X +2980(right)X +3154(to)X +3239(sell)X +3373(without)X +3640(permission,)X +555 960(the)N +679(right)X +856(to)X +944(hoard)X +8 s +1127 935(3)N +10 s +1185 960(and)N +1327(the)X +1451(right)X +1628(to)X +1716(do)X +1821(other)X +2011(icky)X +2174(things)X +2394(as)X +2486(you)X +2631(see)X +2759(\256t\))X +2877(but)X +3004(those)X +3198(rights)X +3405(are)X +3529(also)X +3683(granted)X +3949(to)X +555 1056(everyone)N +870(else.)X +755 1180(Please)N +997(note)X +1172(that)X +1329(all)X +1446(previous)X +1759(distributions)X +2195(of)X +2298(this)X +2449(software)X +2762(contained)X +3110(a)X +3182(copyright)X +3525(\(which)X +3784(is)X +3873(now)X +555 1276(dropped\))N +868(to)X +953(protect)X +1199(its)X +1297(origins)X +1542(and)X +1681(its)X +1779(current)X +2030(public)X +2253(domain)X +2516(status)X +2721(against)X +2970(any)X +3108(possible)X +3392(claims)X +3623(and/or)X +3850(chal-)X +555 1372(lenges.)N +3 f +555 1564(Acknowledgments)N +1 f +755 1688(Many)N +966(people)X +1204(have)X +1380(been)X +1556(very)X +1723(helpful)X +1974(and)X +2114(supportive.)X +2515(A)X +2596(partial)X +2824(list)X +2944(would)X +3167(necessarily)X +3547(include)X +3806(Rayan)X +555 1784(Zacherissen)N +963(\(who)X +1152(contributed)X +1541(the)X +1663(man)X +1824(page,)X +2019(and)X +2158(also)X +2310(hacked)X +2561(a)X +2620(MMAP)X +2887(version)X +3146(of)X +2 f +3236(sdbm)X +1 f +3405(\),)X +3475(Arnold)X +3725(Robbins,)X +555 1880(Chris)N +763(Lewis,)X +1013(Bill)X +1166(Davidsen,)X +1523(Henry)X +1758(Spencer,)X +2071(Geoff)X +2293(Collyer,)X +2587(Rich)X +2772(Salz)X +2944(\(who)X +3143(got)X +3279(me)X +3411(started)X +3659(in)X +3755(the)X +3887(\256rst)X +555 1976(place\),)N +792(Johannes)X +1106(Ruschein)X +1424(\(who)X +1609(did)X +1731(the)X +1849(minix)X +2055(port\))X +2231(and)X +2367(David)X +2583(Tilbrook.)X +2903(I)X +2950(thank)X +3148(you)X +3288(all.)X +3 f +555 2168(Distribution)N +992(Manifest)X +1315(and)X +1463(Notes)X +1 f +555 2292(This)N +717(distribution)X +1105(of)X +2 f +1192(sdbm)X +1 f +1381(includes)X +1668(\(at)X +1773(least\))X +1967(the)X +2085(following:)X +7 f +747 2436(CHANGES)N +1323(change)X +1659(log)X +747 2532(README)N +1323(this)X +1563(file.)X +747 2628(biblio)N +1323(a)X +1419(small)X +1707(bibliography)X +2331(on)X +2475(external)X +2907(hashing)X +747 2724(dba.c)N +1323(a)X +1419(crude)X +1707(\(n/s\)dbm)X +2139(page)X +2379(file)X +2619(analyzer)X +747 2820(dbd.c)N +1323(a)X +1419(crude)X +1707(\(n/s\)dbm)X +2139(page)X +2379(file)X +2619(dumper)X +2955(\(for)X +3195(conversion\))X +747 2916(dbe.1)N +1323(man)X +1515(page)X +1755(for)X +1947(dbe.c)X +747 3012(dbe.c)N +1323(Janick's)X +1755(database)X +2187(editor)X +747 3108(dbm.c)N +1323(a)X +1419(dbm)X +1611(library)X +1995(emulation)X +2475(wrapper)X +2859(for)X +3051(ndbm/sdbm)X +747 3204(dbm.h)N +1323(header)X +1659(file)X +1899(for)X +2091(the)X +2283(above)X +747 3300(dbu.c)N +1323(a)X +1419(crude)X +1707(db)X +1851(management)X +2379(utility)X +747 3396(hash.c)N +1323(hashing)X +1707(function)X +747 3492(makefile)N +1323(guess.)X +747 3588(pair.c)N +1323(page-level)X +1851(routines)X +2283(\(posted)X +2667(earlier\))X +747 3684(pair.h)N +1323(header)X +1659(file)X +1899(for)X +2091(the)X +2283(above)X +747 3780(readme.ms)N +1323(troff)X +1611(source)X +1947(for)X +2139(the)X +2331(README)X +2667(file)X +747 3876(sdbm.3)N +1323(man)X +1515(page)X +747 3972(sdbm.c)N +1323(the)X +1515(real)X +1755(thing)X +747 4068(sdbm.h)N +1323(header)X +1659(file)X +1899(for)X +2091(the)X +2283(above)X +747 4164(tune.h)N +1323(place)X +1611(for)X +1803(tuning)X +2139(&)X +2235(portability)X +2811(thingies)X +747 4260(util.c)N +1323(miscellaneous)X +755 4432(dbu)N +1 f +924(is)X +1002(a)X +1063(simple)X +1301(database)X +1603(manipulation)X +2050(program)X +8 s +2322 4407(4)N +10 s +2379 4432(that)N +2524(tries)X +2687(to)X +2774(look)X +2941(like)X +3086(Bell)X +3244(Labs')X +7 f +3480(cbt)X +1 f +3649(utility.)X +3884(It)X +3958(is)X +555 4528(currently)N +867(incomplete)X +1245(in)X +1329(functionality.)X +1800(I)X +1849(use)X +7 f +2006(dbu)X +1 f +2172(to)X +2255(test)X +2387(out)X +2510(the)X +2629(routines:)X +2930(it)X +2995(takes)X +3181(\(from)X +3385(stdin\))X +3588(tab)X +3707(separated)X +555 4624(key/value)N +898(pairs)X +1085(for)X +1210(commands)X +1587(like)X +7 f +1765(build)X +1 f +2035(or)X +7 f +2160(insert)X +1 f +2478(or)X +2575(takes)X +2770(keys)X +2947(for)X +3071(commands)X +3448(like)X +7 f +3626(delete)X +1 f +3944(or)X +7 f +555 4720(look)N +1 f +(.)S +7 f +747 4864(dbu)N +939(<build|creat|look|insert|cat|delete>)X +2715(dbmfile)X +755 5036(dba)N +1 f +927(is)X +1008(a)X +1072(crude)X +1279(analyzer)X +1580(of)X +2 f +1675(dbm/sdbm/ndbm)X +1 f +2232(page)X +2412(\256les.)X +2593(It)X +2670(scans)X +2872(the)X +2998(entire)X +3209(page)X +3389(\256le,)X +3538(reporting)X +3859(page)X +555 5132(level)N +731(statistics,)X +1046(and)X +1182(totals)X +1375(at)X +1453(the)X +1571(end.)X +7 f +755 5256(dbd)N +1 f +925(is)X +1004(a)X +1066(crude)X +1271(dump)X +1479(program)X +1777(for)X +2 f +1897(dbm/ndbm/sdbm)X +1 f +2452(databases.)X +2806(It)X +2881(ignores)X +3143(the)X +3267(bitmap,)X +3534(and)X +3675(dumps)X +3913(the)X +555 5352(data)N +717(pages)X +928(in)X +1018(sequence.)X +1361(It)X +1437(can)X +1576(be)X +1679(used)X +1853(to)X +1942(create)X +2162(input)X +2353(for)X +2474(the)X +7 f +2627(dbu)X +1 f +2798(utility.)X +3055(Note)X +3238(that)X +7 f +3413(dbd)X +1 f +3584(will)X +3735(skip)X +3895(any)X +8 s +10 f +555 5432(hhhhhhhhhhhhhhhhhh)N +6 s +1 f +635 5507(3)N +8 s +691 5526(You)N +817(cannot)X +1003(really)X +1164(hoard)X +1325(something)X +1608(that)X +1720(is)X +1779(available)X +2025(to)X +2091(the)X +2185(public)X +2361(at)X +2423(large,)X +2582(but)X +2680(try)X +2767(if)X +2822(it)X +2874(makes)X +3053(you)X +3165(feel)X +3276(any)X +3384(better.)X +6 s +635 5601(4)N +8 s +691 5620(The)N +7 f +829(dbd)X +1 f +943(,)X +7 f +998(dba)X +1 f +1112(,)X +7 f +1167(dbu)X +1 f +1298(utilities)X +1508(are)X +1602(quick)X +1761(hacks)X +1923(and)X +2032(are)X +2126(not)X +2225(\256t)X +2295(for)X +2385(production)X +2678(use.)X +2795(They)X +2942(were)X +3081(developed)X +3359(late)X +3467(one)X +3575(night,)X +555 5700(just)N +664(to)X +730(test)X +835(out)X +2 f +933(sdbm)X +1 f +1068(,)X +1100(and)X +1208(convert)X +1415(some)X +1566(databases.)X + +3 p +%%Page: 3 3 +8 s 0 xH 0 xS 1 f +10 s +2216 384(-)N +2263(3)X +2323(-)X +555 672(NULLs)N +821(in)X +903(the)X +1021(key)X +1157(and)X +1293(data)X +1447(\256elds,)X +1660(thus)X +1813(is)X +1886(unsuitable)X +2235(to)X +2317(convert)X +2578(some)X +2767(peculiar)X +3046(databases)X +3374(that)X +3514(insist)X +3702(in)X +3784(includ-)X +555 768(ing)N +677(the)X +795(terminating)X +1184(null.)X +755 892(I)N +841(have)X +1052(also)X +1240(included)X +1575(a)X +1670(copy)X +1885(of)X +2011(the)X +7 f +2195(dbe)X +1 f +2397(\()X +2 f +2424(ndbm)X +1 f +2660(DataBase)X +3026(Editor\))X +3311(by)X +3449(Janick)X +3712(Bergeron)X +555 988([janick@bnr.ca])N +1098(for)X +1212(your)X +1379(pleasure.)X +1687(You)X +1845(may)X +2003(\256nd)X +2147(it)X +2211(more)X +2396(useful)X +2612(than)X +2770(the)X +2888(little)X +7 f +3082(dbu)X +1 f +3246(utility.)X +7 f +755 1112(dbm.[ch])N +1 f +1169(is)X +1252(a)X +2 f +1318(dbm)X +1 f +1486(library)X +1730(emulation)X +2079(on)X +2188(top)X +2319(of)X +2 f +2415(ndbm)X +1 f +2622(\(and)X +2794(hence)X +3011(suitable)X +3289(for)X +2 f +3412(sdbm)X +1 f +3581(\).)X +3657(Written)X +3931(by)X +555 1208(Robert)N +793(Elz.)X +755 1332(The)N +2 f +901(sdbm)X +1 f +1090(library)X +1324(has)X +1451(been)X +1623(around)X +1866(in)X +1948(beta)X +2102(test)X +2233(for)X +2347(quite)X +2527(a)X +2583(long)X +2745(time,)X +2927(and)X +3063(from)X +3239(whatever)X +3554(little)X +3720(feedback)X +555 1428(I)N +609(received)X +909(\(maybe)X +1177(no)X +1284(news)X +1476(is)X +1555(good)X +1741(news\),)X +1979(I)X +2032(believe)X +2290(it)X +2360(has)X +2493(been)X +2671(functioning)X +3066(without)X +3336(any)X +3478(signi\256cant)X +3837(prob-)X +555 1524(lems.)N +752(I)X +805(would,)X +1051(of)X +1144(course,)X +1400(appreciate)X +1757(all)X +1863(\256xes)X +2040(and/or)X +2271(improvements.)X +2774(Portability)X +3136(enhancements)X +3616(would)X +3841(espe-)X +555 1620(cially)N +753(be)X +849(useful.)X +3 f +555 1812(Implementation)N +1122(Issues)X +1 f +755 1936(Hash)N +944(functions:)X +1288(The)X +1437(algorithm)X +1772(behind)X +2 f +2014(sdbm)X +1 f +2207(implementation)X +2733(needs)X +2939(a)X +2998(good)X +3181(bit-scrambling)X +3671(hash)X +3841(func-)X +555 2032(tion)N +702(to)X +787(be)X +886(effective.)X +1211(I)X +1261(ran)X +1387(into)X +1534(a)X +1593(set)X +1705(of)X +1795(constants)X +2116(for)X +2233(a)X +2292(simple)X +2528(hash)X +2698(function)X +2988(that)X +3130(seem)X +3317(to)X +3401(help)X +2 f +3561(sdbm)X +1 f +3752(perform)X +555 2128(better)N +758(than)X +2 f +916(ndbm)X +1 f +1114(for)X +1228(various)X +1484(inputs:)X +7 f +747 2272(/*)N +795 2368(*)N +891(polynomial)X +1419(conversion)X +1947(ignoring)X +2379(overflows)X +795 2464(*)N +891(65599)X +1179(nice.)X +1467(65587)X +1755(even)X +1995(better.)X +795 2560(*/)N +747 2656(long)N +747 2752(dbm_hash\(char)N +1419(*str,)X +1707(int)X +1899(len\))X +2139({)X +939 2848(register)N +1371(unsigned)X +1803(long)X +2043(n)X +2139(=)X +2235(0;)X +939 3040(while)N +1227(\(len--\))X +1131 3136(n)N +1227(=)X +1323(n)X +1419(*)X +1515(65599)X +1803(+)X +1899(*str++;)X +939 3232(return)N +1275(n;)X +747 3328(})N +1 f +755 3500(There)N +975(may)X +1145(be)X +1253(better)X +1467(hash)X +1645(functions)X +1974(for)X +2099(the)X +2228(purposes)X +2544(of)X +2642(dynamic)X +2949(hashing.)X +3269(Try)X +3416(your)X +3594(favorite,)X +3895(and)X +555 3596(check)N +766(the)X +887(page\256le.)X +1184(If)X +1261(it)X +1328(contains)X +1618(too)X +1743(many)X +1944(pages)X +2150(with)X +2315(too)X +2440(many)X +2641(holes,)X +2853(\(in)X +2965(relation)X +3233(to)X +3318(this)X +3456(one)X +3595(for)X +3712(example\))X +555 3692(or)N +656(if)X +2 f +739(sdbm)X +1 f +942(simply)X +1193(stops)X +1391(working)X +1692(\(fails)X +1891(after)X +7 f +2101(SPLTMAX)X +1 f +2471(attempts)X +2776(to)X +2872(split\))X +3070(when)X +3278(you)X +3432(feed)X +3604(your)X +3784(NEWS)X +7 f +555 3788(history)N +1 f +912(\256le)X +1035(to)X +1118(it,)X +1203(you)X +1344(probably)X +1650(do)X +1751(not)X +1874(have)X +2047(a)X +2104(good)X +2285(hashing)X +2555(function.)X +2883(If)X +2958(you)X +3099(do)X +3200(better)X +3404(\(for)X +3545(different)X +3842(types)X +555 3884(of)N +642(input\),)X +873(I)X +920(would)X +1140(like)X +1280(to)X +1362(know)X +1560(about)X +1758(the)X +1876(function)X +2163(you)X +2303(use.)X +755 4008(Block)N +967(sizes:)X +1166(It)X +1236(seems)X +1453(\(from)X +1657(various)X +1914(tests)X +2077(on)X +2178(a)X +2235(few)X +2377(machines\))X +2727(that)X +2867(a)X +2923(page)X +3095(\256le)X +3217(block)X +3415(size)X +7 f +3588(PBLKSIZ)X +1 f +3944(of)X +555 4104(1024)N +738(is)X +814(by)X +917(far)X +1030(the)X +1150(best)X +1301(for)X +1417(performance,)X +1866(but)X +1990(this)X +2127(also)X +2278(happens)X +2563(to)X +2647(limit)X +2819(the)X +2939(size)X +3086(of)X +3175(a)X +3233(key/value)X +3567(pair.)X +3734(Depend-)X +555 4200(ing)N +681(on)X +785(your)X +956(needs,)X +1183(you)X +1327(may)X +1489(wish)X +1663(to)X +1748(increase)X +2035(the)X +2156(page)X +2331(size,)X +2499(and)X +2638(also)X +2790(adjust)X +7 f +3032(PAIRMAX)X +1 f +3391(\(the)X +3539(maximum)X +3886(size)X +555 4296(of)N +648(a)X +710(key/value)X +1048(pair)X +1199(allowed:)X +1501(should)X +1740(always)X +1989(be)X +2090(at)X +2173(least)X +2345(three)X +2531(words)X +2752(smaller)X +3013(than)X +7 f +3204(PBLKSIZ)X +1 f +(.\))S +3612(accordingly.)X +555 4392(The)N +706(system-wide)X +1137(version)X +1399(of)X +1492(the)X +1616(library)X +1856(should)X +2095(probably)X +2406(be)X +2508(con\256gured)X +2877(with)X +3044(1024)X +3229(\(distribution)X +3649(default\),)X +3944(as)X +555 4488(this)N +690(appears)X +956(to)X +1038(be)X +1134(suf\256cient)X +1452(for)X +1566(most)X +1741(common)X +2041(uses)X +2199(of)X +2 f +2286(sdbm)X +1 f +2455(.)X +3 f +555 4680(Portability)N +1 f +755 4804(This)N +917(package)X +1201(has)X +1328(been)X +1500(tested)X +1707(in)X +1789(many)X +1987(different)X +2284(UN*Xes)X +2585(even)X +2757(including)X +3079(minix,)X +3305(and)X +3441(appears)X +3707(to)X +3789(be)X +3885(rea-)X +555 4900(sonably)N +824(portable.)X +1127(This)X +1289(does)X +1456(not)X +1578(mean)X +1772(it)X +1836(will)X +1980(port)X +2129(easily)X +2336(to)X +2418(non-UN*X)X +2799(systems.)X +3 f +555 5092(Notes)N +767(and)X +915(Miscellaneous)X +1 f +755 5216(The)N +2 f +913(sdbm)X +1 f +1115(is)X +1201(not)X +1336(a)X +1405(very)X +1581(complicated)X +2006(package,)X +2323(at)X +2414(least)X +2594(not)X +2729(after)X +2910(you)X +3063(familiarize)X +3444(yourself)X +3739(with)X +3913(the)X +555 5312(literature)N +879(on)X +993(external)X +1286(hashing.)X +1589(There)X +1811(are)X +1944(other)X +2143(interesting)X +2514(algorithms)X +2889(in)X +2984(existence)X +3316(that)X +3469(ensure)X +3712(\(approxi-)X +555 5408(mately\))N +825(single-read)X +1207(access)X +1438(to)X +1525(a)X +1586(data)X +1745(value)X +1944(associated)X +2299(with)X +2466(any)X +2607(key.)X +2768(These)X +2984(are)X +3107(directory-less)X +3568(schemes)X +3864(such)X +555 5504(as)N +2 f +644(linear)X +857(hashing)X +1 f +1132([Lit80])X +1381(\(+)X +1475(Larson)X +1720(variations\),)X +2 f +2105(spiral)X +2313(storage)X +1 f +2575([Mar79])X +2865(or)X +2954(directory)X +3265(schemes)X +3558(such)X +3726(as)X +2 f +3814(exten-)X +555 5600(sible)N +731(hashing)X +1 f +1009([Fag79])X +1288(by)X +1393(Fagin)X +1600(et)X +1683(al.)X +1786(I)X +1838(do)X +1943(hope)X +2124(these)X +2314(sources)X +2579(provide)X +2848(a)X +2908(reasonable)X +3276(playground)X +3665(for)X +3783(experi-)X +555 5696(mentation)N +907(with)X +1081(other)X +1277(algorithms.)X +1690(See)X +1837(the)X +1966(June)X +2144(1988)X +2335(issue)X +2526(of)X +2624(ACM)X +2837(Computing)X +3227(Surveys)X +3516([Enb88])X +3810(for)X +3935(an)X +555 5792(excellent)N +865(overview)X +1184(of)X +1271(the)X +1389(\256eld.)X + +4 p +%%Page: 4 4 +10 s 0 xH 0 xS 1 f +2216 384(-)N +2263(4)X +2323(-)X +3 f +555 672(References)N +1 f +555 824([Lar78])N +875(P.-A.)X +1064(Larson,)X +1327(``Dynamic)X +1695(Hashing'',)X +2 f +2056(BIT)X +1 f +(,)S +2216(vol.)X +2378(18,)X +2518(pp.)X +2638(184-201,)X +2945(1978.)X +555 948([Tho90])N +875(Ken)X +1029(Thompson,)X +2 f +1411(private)X +1658(communication)X +1 f +2152(,)X +2192(Nov.)X +2370(1990)X +555 1072([Lit80])N +875(W.)X +992(Litwin,)X +1246(``)X +1321(Linear)X +1552(Hashing:)X +1862(A)X +1941(new)X +2096(tool)X +2261(for)X +2396(\256le)X +2539(and)X +2675(table)X +2851(addressing'',)X +2 f +3288(Proceedings)X +3709(of)X +3791(the)X +3909(6th)X +875 1168(Conference)N +1269(on)X +1373(Very)X +1548(Large)X +1782(Dabatases)X +2163(\(Montreal\))X +1 f +2515(,)X +2558(pp.)X +2701(212-223,)X +3031(Very)X +3215(Large)X +3426(Database)X +3744(Founda-)X +875 1264(tion,)N +1039(Saratoga,)X +1360(Calif.,)X +1580(1980.)X +555 1388([Fag79])N +875(R.)X +969(Fagin,)X +1192(J.)X +1284(Nievergelt,)X +1684(N.)X +1803(Pippinger,)X +2175(and)X +2332(H.)X +2451(R.)X +2544(Strong,)X +2797(``Extendible)X +3218(Hashing)X +3505(-)X +3552(A)X +3630(Fast)X +3783(Access)X +875 1484(Method)N +1144(for)X +1258(Dynamic)X +1572(Files'',)X +2 f +1821(ACM)X +2010(Trans.)X +2236(Database)X +2563(Syst.)X +1 f +2712(,)X +2752(vol.)X +2894(4,)X +2994(no.3,)X +3174(pp.)X +3294(315-344,)X +3601(Sept.)X +3783(1979.)X +555 1608([Wal84])N +875(Rich)X +1055(Wales,)X +1305(``Discussion)X +1739(of)X +1835("dbm")X +2072(data)X +2235(base)X +2406(system'',)X +2 f +2730(USENET)X +3051(newsgroup)X +3430(unix.wizards)X +1 f +3836(,)X +3884(Jan.)X +875 1704(1984.)N +555 1828([Tor87])N +875(Chris)X +1068(Torek,)X +1300(``Re:)X +1505(dbm.a)X +1743(and)X +1899(ndbm.a)X +2177(archives'',)X +2 f +2539(USENET)X +2852(newsgroup)X +3223(comp.unix)X +1 f +3555(,)X +3595(1987.)X +555 1952([Mar79])N +875(G.)X +974(N.)X +1073(Martin,)X +1332(``Spiral)X +1598(Storage:)X +1885(Incrementally)X +2371(Augmentable)X +2843(Hash)X +3048(Addressed)X +3427(Storage'',)X +2 f +3766(Techni-)X +875 2048(cal)N +993(Report)X +1231(#27)X +1 f +(,)S +1391(University)X +1749(of)X +1836(Varwick,)X +2153(Coventry,)X +2491(U.K.,)X +2687(1979.)X +555 2172([Enb88])N +875(R.)X +977(J.)X +1057(Enbody)X +1335(and)X +1480(H.)X +1586(C.)X +1687(Du,)X +1833(``Dynamic)X +2209(Hashing)X +2524(Schemes'',)X +2 f +2883(ACM)X +3080(Computing)X +3463(Surveys)X +1 f +3713(,)X +3761(vol.)X +3911(20,)X +875 2268(no.)N +995(2,)X +1075(pp.)X +1195(85-113,)X +1462(June)X +1629(1988.)X + +4 p +%%Trailer +xt + +xs diff --git a/ext/SDBM_File/sdbm/sdbm.3 b/ext/SDBM_File/sdbm/sdbm.3 new file mode 100644 index 0000000000..f0f2d07c84 --- /dev/null +++ b/ext/SDBM_File/sdbm/sdbm.3 @@ -0,0 +1,290 @@ +.\" $Id: sdbm.3,v 1.2 90/12/13 13:00:57 oz Exp $ +.TH SDBM 3 "1 March 1990" +.SH NAME +sdbm, 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 +.SH SYNOPSIS +.nf +.ft B +#include <sdbm.h> +.sp +typedef struct { + char *dptr; + int dsize; +} datum; +.sp +datum nullitem = { NULL, 0 }; +.sp +\s-1DBM\s0 *dbm_open(char *file, int flags, int mode) +.sp +\s-1DBM\s0 *dbm_prep(char *dirname, char *pagname, int flags, int mode) +.sp +void dbm_close(\s-1DBM\s0 *db) +.sp +datum dbm_fetch(\s-1DBM\s0 *db, key) +.sp +int dbm_store(\s-1DBM\s0 *db, datum key, datum val, int flags) +.sp +int dbm_delete(\s-1DBM\s0 *db, datum key) +.sp +datum dbm_firstkey(\s-1DBM\s0 *db) +.sp +datum dbm_nextkey(\s-1DBM\s0 *db) +.sp +long dbm_hash(char *string, int len) +.sp +int dbm_rdonly(\s-1DBM\s0 *db) +int dbm_error(\s-1DBM\s0 *db) +dbm_clearerr(\s-1DBM\s0 *db) +int dbm_dirfno(\s-1DBM\s0 *db) +int dbm_pagfno(\s-1DBM\s0 *db) +.ft R +.fi +.SH DESCRIPTION +.IX "database library" sdbm "" "\fLsdbm\fR" +.IX dbm_open "" "\fLdbm_open\fR \(em open \fLsdbm\fR database" +.IX dbm_prep "" "\fLdbm_prep\fR \(em prepare \fLsdbm\fR database" +.IX dbm_close "" "\fLdbm_close\fR \(em close \fLsdbm\fR routine" +.IX dbm_fetch "" "\fLdbm_fetch\fR \(em fetch \fLsdbm\fR database data" +.IX dbm_store "" "\fLdbm_store\fR \(em add data to \fLsdbm\fR database" +.IX dbm_delete "" "\fLdbm_delete\fR \(em remove data from \fLsdbm\fR database" +.IX dbm_firstkey "" "\fLdbm_firstkey\fR \(em access \fLsdbm\fR database" +.IX dbm_nextkey "" "\fLdbm_nextkey\fR \(em access \fLsdbm\fR database" +.IX dbm_hash "" "\fLdbm_hash\fR \(em string hash for \fLsdbm\fR database" +.IX dbm_rdonly "" "\fLdbm_rdonly\fR \(em return \fLsdbm\fR database read-only mode" +.IX dbm_error "" "\fLdbm_error\fR \(em return \fLsdbm\fR database error condition" +.IX dbm_clearerr "" "\fLdbm_clearerr\fR \(em clear \fLsdbm\fR database error condition" +.IX dbm_dirfno "" "\fLdbm_dirfno\fR \(em return \fLsdbm\fR database bitmap file descriptor" +.IX dbm_pagfno "" "\fLdbm_pagfno\fR \(em return \fLsdbm\fR database data file descriptor" +.IX "database functions \(em \fLsdbm\fR" dbm_open "" \fLdbm_open\fP +.IX "database functions \(em \fLsdbm\fR" dbm_prep "" \fLdbm_prep\fP +.IX "database functions \(em \fLsdbm\fR" dbm_close "" \fLdbm_close\fP +.IX "database functions \(em \fLsdbm\fR" dbm_fetch "" \fLdbm_fetch\fP +.IX "database functions \(em \fLsdbm\fR" dbm_store "" \fLdbm_store\fP +.IX "database functions \(em \fLsdbm\fR" dbm_delete "" \fLdbm_delete\fP +.IX "database functions \(em \fLsdbm\fR" dbm_firstkey "" \fLdbm_firstkey\fP +.IX "database functions \(em \fLsdbm\fR" dbm_nextkey "" \fLdbm_nextkey\fP +.IX "database functions \(em \fLsdbm\fR" dbm_rdonly "" \fLdbm_rdonly\fP +.IX "database functions \(em \fLsdbm\fR" dbm_error "" \fLdbm_error\fP +.IX "database functions \(em \fLsdbm\fR" dbm_clearerr "" \fLdbm_clearerr\fP +.IX "database functions \(em \fLsdbm\fR" dbm_dirfno "" \fLdbm_dirfno\fP +.IX "database functions \(em \fLsdbm\fR" dbm_pagfno "" \fLdbm_pagfno\fP +.LP +This package allows an application to maintain a mapping of <key,value> pairs +in disk files. This is not to be considered a real database system, but is +still useful in many simple applications built around fast retrieval of a data +value from a key. This implementation uses an external hashing scheme, +called Dynamic Hashing, as described by Per-Aake Larson in BIT 18 (1978) pp. +184-201. Retrieval of any item usually requires a single disk access. +The application interface is compatible with the +.IR ndbm (3) +library. +.LP +An +.B sdbm +database is kept in two files usually given the extensions +.B \.dir +and +.BR \.pag . +The +.B \.dir +file contains a bitmap representing a forest of binary hash trees, the leaves +of which indicate data pages in the +.B \.pag +file. +.LP +The application interface uses the +.B datum +structure to describe both +.I keys +and +.IR value s. +A +.B datum +specifies a byte sequence of +.I dsize +size pointed to by +.IR dptr . +If you use +.SM ASCII +strings as +.IR key s +or +.IR value s, +then you must decide whether or not to include the terminating +.SM NUL +byte which sometimes defines strings. Including it will require larger +database files, but it will be possible to get sensible output from a +.IR strings (1) +command applied to the data file. +.LP +In order to allow a process using this package to manipulate multiple +databases, the applications interface always requires a +.IR handle , +a +.BR "DBM *" , +to identify the database to be manipulated. Such a handle can be obtained +from the only routines that do not require it, namely +.BR dbm_open (\|) +or +.BR dbm_prep (\|). +Either of these will open or create the two necessary files. The +difference is that the latter allows explicitly naming the bitmap and data +files whereas +.BR dbm_open (\|) +will take a base file name and call +.BR dbm_prep (\|) +with the default extensions. +The +.I flags +and +.I mode +parameters are the same as for +.BR open (2). +.LP +To free the resources occupied while a database handle is active, call +.BR dbm_close (\|). +.LP +Given a handle, one can retrieve data associated with a key by using the +.BR dbm_fetch (\|) +routine, and associate data with a key by using the +.BR dbm_store (\|) +routine. +.LP +The values of the +.I flags +parameter for +.BR dbm_store (\|) +can be either +.BR \s-1DBM_INSERT\s0 , +which will not change an existing entry with the same key, or +.BR \s-1DBM_REPLACE\s0 , +which will replace an existing entry with the same key. +Keys are unique within the database. +.LP +To delete a key and its associated value use the +.BR dbm_delete (\|) +routine. +.LP +To retrieve every key in the database, use a loop like: +.sp +.nf +.ft B +for (key = dbm_firstkey(db); key.dptr != NULL; key = dbm_nextkey(db)) + ; +.ft R +.fi +.LP +The order of retrieval is unspecified. +.LP +If you determine that the performance of the database is inadequate or +you notice clustering or other effects that may be due to the hashing +algorithm used by this package, you can override it by supplying your +own +.BR dbm_hash (\|) +routine. Doing so will make the database unintelligable to any other +applications that do not use your specialized hash function. +.sp +.LP +The following macros are defined in the header file: +.IP +.BR dbm_rdonly (\|) +returns true if the database has been opened read\-only. +.IP +.BR dbm_error (\|) +returns true if an I/O error has occurred. +.IP +.BR dbm_clearerr (\|) +allows you to clear the error flag if you think you know what the error +was and insist on ignoring it. +.IP +.BR dbm_dirfno (\|) +returns the file descriptor associated with the bitmap file. +.IP +.BR dbm_pagfno (\|) +returns the file descriptor associated with the data file. +.SH SEE ALSO +.IR open (2). +.SH DIAGNOSTICS +Functions that return a +.B "DBM *" +handle will use +.SM NULL +to indicate an error. +Functions that return an +.B int +will use \-1 to indicate an error. The normal return value in that case is 0. +Functions that return a +.B datum +will return +.B nullitem +to indicate an error. +.LP +As a special case of +.BR dbm_store (\|), +if it is called with the +.B \s-1DBM_INSERT\s0 +flag and the key already exists in the database, the return value will be 1. +.LP +In general, if a function parameter is invalid, +.B errno +will be set to +.BR \s-1EINVAL\s0 . +If a write operation is requested on a read-only database, +.B errno +will be set to +.BR \s-1ENOPERM\s0 . +If a memory allocation (using +.IR malloc (3)) +failed, +.B errno +will be set to +.BR \s-1ENOMEM\s0 . +For I/O operation failures +.B errno +will contain the value set by the relevant failed system call, either +.IR read (2), +.IR write (2), +or +.IR lseek (2). +.SH AUTHOR +.IP "Ozan S. Yigit" (oz@nexus.yorku.ca) +.SH BUGS +The sum of key and value data sizes must not exceed +.B \s-1PAIRMAX\s0 +(1008 bytes). +.LP +The sum of the key and value data sizes where several keys hash to the +same value must fit within one bitmap page. +.LP +The +.B \.pag +file will contain holes, so its apparent size is larger than its contents. +When copied through the filesystem the holes will be filled. +.LP +The contents of +.B datum +values returned are in volatile storage. If you want to retain the values +pointed to, you must copy them immediately before another call to this package. +.LP +The only safe way for multiple processes to (read and) update a database at +the same time, is to implement a private locking scheme outside this package +and open and close the database between lock acquisitions. It is safe for +multiple processes to concurrently access a database read-only. +.SH APPLICATIONS PORTABILITY +For complete source code compatibility with the Berkeley Unix +.IR ndbm (3) +library, the +.B sdbm.h +header file should be installed in +.BR /usr/include/ndbm.h . +.LP +The +.B nullitem +data item, and the +.BR dbm_prep (\|), +.BR dbm_hash (\|), +.BR dbm_rdonly (\|), +.BR dbm_dirfno (\|), +and +.BR dbm_pagfno (\|) +functions are unique to this package. diff --git a/ext/SDBM_File/sdbm/sdbm.c b/ext/SDBM_File/sdbm/sdbm.c new file mode 100644 index 0000000000..d09adccdd3 --- /dev/null +++ b/ext/SDBM_File/sdbm/sdbm.c @@ -0,0 +1,520 @@ +/* + * sdbm - ndbm work-alike hashed database library + * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). + * author: oz@nexus.yorku.ca + * status: public domain. + * + * core routines + */ + +#ifndef lint +static char rcsid[] = "$Id: sdbm.c,v 1.16 90/12/13 13:01:31 oz Exp $"; +#endif + +#include "config.h" +#include "sdbm.h" +#include "tune.h" +#include "pair.h" + +#ifdef I_FCNTL +# include <fcntl.h> +#endif +#ifdef I_SYS_FILE +# include <sys/file.h> +#endif + +#ifdef I_STRING +# include <string.h> +#else +# include <strings.h> +#endif + +/* + * externals + */ +#ifndef sun +extern int errno; +#endif + +extern Malloc_t malloc proto((MEM_SIZE)); +extern void free proto((void *)); +extern Off_t lseek(); + +/* + * forward + */ +static int getdbit proto((DBM *, long)); +static int setdbit proto((DBM *, long)); +static int getpage proto((DBM *, long)); +static datum getnext proto((DBM *)); +static int makroom proto((DBM *, long, int)); + +/* + * useful macros + */ +#define bad(x) ((x).dptr == NULL || (x).dsize < 0) +#define exhash(item) sdbm_hash((item).dptr, (item).dsize) +#define ioerr(db) ((db)->flags |= DBM_IOERR) + +#define OFF_PAG(off) (long) (off) * PBLKSIZ +#define OFF_DIR(off) (long) (off) * DBLKSIZ + +static long masks[] = { + 000000000000, 000000000001, 000000000003, 000000000007, + 000000000017, 000000000037, 000000000077, 000000000177, + 000000000377, 000000000777, 000000001777, 000000003777, + 000000007777, 000000017777, 000000037777, 000000077777, + 000000177777, 000000377777, 000000777777, 000001777777, + 000003777777, 000007777777, 000017777777, 000037777777, + 000077777777, 000177777777, 000377777777, 000777777777, + 001777777777, 003777777777, 007777777777, 017777777777 +}; + +datum nullitem = {NULL, 0}; + +DBM * +sdbm_open(file, flags, mode) +register char *file; +register int flags; +register int mode; +{ + register DBM *db; + register char *dirname; + register char *pagname; + register int n; + + if (file == NULL || !*file) + return errno = EINVAL, (DBM *) NULL; +/* + * need space for two seperate filenames + */ + n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2; + + if ((dirname = malloc((unsigned) n)) == NULL) + return errno = ENOMEM, (DBM *) NULL; +/* + * build the file names + */ + dirname = strcat(strcpy(dirname, file), DIRFEXT); + pagname = strcpy(dirname + strlen(dirname) + 1, file); + pagname = strcat(pagname, PAGFEXT); + + db = sdbm_prep(dirname, pagname, flags, mode); + free((char *) dirname); + return db; +} + +DBM * +sdbm_prep(dirname, pagname, flags, mode) +char *dirname; +char *pagname; +int flags; +int mode; +{ + register DBM *db; + struct stat dstat; + + if ((db = (DBM *) malloc(sizeof(DBM))) == NULL) + return errno = ENOMEM, (DBM *) NULL; + + db->flags = 0; + db->hmask = 0; + db->blkptr = 0; + db->keyptr = 0; +/* + * adjust user flags so that WRONLY becomes RDWR, + * as required by this package. Also set our internal + * flag for RDONLY if needed. + */ + if (flags & O_WRONLY) + flags = (flags & ~O_WRONLY) | O_RDWR; + + else if ((flags & 03) == O_RDONLY) + db->flags = DBM_RDONLY; +/* + * open the files in sequence, and stat the dirfile. + * If we fail anywhere, undo everything, return NULL. + */ + if ((db->pagf = open(pagname, flags, mode)) > -1) { + if ((db->dirf = open(dirname, flags, mode)) > -1) { +/* + * need the dirfile size to establish max bit number. + */ + if (fstat(db->dirf, &dstat) == 0) { +/* + * zero size: either a fresh database, or one with a single, + * unsplit data page: dirpage is all zeros. + */ + db->dirbno = (!dstat.st_size) ? 0 : -1; + db->pagbno = -1; + db->maxbno = dstat.st_size * BYTESIZ; + + (void) memset(db->pagbuf, 0, PBLKSIZ); + (void) memset(db->dirbuf, 0, DBLKSIZ); + /* + * success + */ + return db; + } + (void) close(db->dirf); + } + (void) close(db->pagf); + } + free((char *) db); + return (DBM *) NULL; +} + +void +sdbm_close(db) +register DBM *db; +{ + if (db == NULL) + errno = EINVAL; + else { + (void) close(db->dirf); + (void) close(db->pagf); + free((char *) db); + } +} + +datum +sdbm_fetch(db, key) +register DBM *db; +datum key; +{ + if (db == NULL || bad(key)) + return errno = EINVAL, nullitem; + + if (getpage(db, exhash(key))) + return getpair(db->pagbuf, key); + + return ioerr(db), nullitem; +} + +int +sdbm_delete(db, key) +register DBM *db; +datum key; +{ + if (db == NULL || bad(key)) + return errno = EINVAL, -1; + if (sdbm_rdonly(db)) + return errno = EPERM, -1; + + if (getpage(db, exhash(key))) { + if (!delpair(db->pagbuf, key)) + return -1; +/* + * update the page file + */ + if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 + || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) + return ioerr(db), -1; + + return 0; + } + + return ioerr(db), -1; +} + +int +sdbm_store(db, key, val, flags) +register DBM *db; +datum key; +datum val; +int flags; +{ + int need; + register long hash; + + if (db == NULL || bad(key)) + return errno = EINVAL, -1; + if (sdbm_rdonly(db)) + return errno = EPERM, -1; + + need = key.dsize + val.dsize; +/* + * is the pair too big (or too small) for this database ?? + */ + if (need < 0 || need > PAIRMAX) + return errno = EINVAL, -1; + + if (getpage(db, (hash = exhash(key)))) { +/* + * if we need to replace, delete the key/data pair + * first. If it is not there, ignore. + */ + if (flags == DBM_REPLACE) + (void) delpair(db->pagbuf, key); +#ifdef SEEDUPS + else if (duppair(db->pagbuf, key)) + return 1; +#endif +/* + * if we do not have enough room, we have to split. + */ + if (!fitpair(db->pagbuf, need)) + if (!makroom(db, hash, need)) + return ioerr(db), -1; +/* + * we have enough room or split is successful. insert the key, + * and update the page file. + */ + (void) putpair(db->pagbuf, key, val); + + if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 + || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) + return ioerr(db), -1; + /* + * success + */ + return 0; + } + + return ioerr(db), -1; +} + +/* + * makroom - make room by splitting the overfull page + * this routine will attempt to make room for SPLTMAX times before + * giving up. + */ +static int +makroom(db, hash, need) +register DBM *db; +long hash; +int need; +{ + long newp; + char twin[PBLKSIZ]; + char *pag = db->pagbuf; + char *new = twin; + register int smax = SPLTMAX; + + do { +/* + * split the current page + */ + (void) splpage(pag, new, db->hmask + 1); +/* + * address of the new page + */ + newp = (hash & db->hmask) | (db->hmask + 1); + +/* + * write delay, read avoidence/cache shuffle: + * select the page for incoming pair: if key is to go to the new page, + * write out the previous one, and copy the new one over, thus making + * it the current page. If not, simply write the new page, and we are + * still looking at the page of interest. current page is not updated + * here, as sdbm_store will do so, after it inserts the incoming pair. + */ + if (hash & (db->hmask + 1)) { + if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 + || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) + return 0; + db->pagbno = newp; + (void) memcpy(pag, new, PBLKSIZ); + } + else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0 + || write(db->pagf, new, PBLKSIZ) < 0) + return 0; + + if (!setdbit(db, db->curbit)) + return 0; +/* + * see if we have enough room now + */ + if (fitpair(pag, need)) + return 1; +/* + * try again... update curbit and hmask as getpage would have + * done. because of our update of the current page, we do not + * need to read in anything. BUT we have to write the current + * [deferred] page out, as the window of failure is too great. + */ + db->curbit = 2 * db->curbit + + ((hash & (db->hmask + 1)) ? 2 : 1); + db->hmask |= db->hmask + 1; + + if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 + || write(db->pagf, db->pagbuf, PBLKSIZ) < 0) + return 0; + + } while (--smax); +/* + * if we are here, this is real bad news. After SPLTMAX splits, + * we still cannot fit the key. say goodnight. + */ +#ifdef BADMESS + (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44); +#endif + return 0; + +} + +/* + * the following two routines will break if + * deletions aren't taken into account. (ndbm bug) + */ +datum +sdbm_firstkey(db) +register DBM *db; +{ + if (db == NULL) + return errno = EINVAL, nullitem; +/* + * start at page 0 + */ + if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0 + || read(db->pagf, db->pagbuf, PBLKSIZ) < 0) + return ioerr(db), nullitem; + db->pagbno = 0; + db->blkptr = 0; + db->keyptr = 0; + + return getnext(db); +} + +datum +sdbm_nextkey(db) +register DBM *db; +{ + if (db == NULL) + return errno = EINVAL, nullitem; + return getnext(db); +} + +/* + * all important binary trie traversal + */ +static int +getpage(db, hash) +register DBM *db; +register long hash; +{ + register int hbit; + register long dbit; + register long pagb; + + dbit = 0; + hbit = 0; + while (dbit < db->maxbno && getdbit(db, dbit)) + dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1); + + debug(("dbit: %d...", dbit)); + + db->curbit = dbit; + db->hmask = masks[hbit]; + + pagb = hash & db->hmask; +/* + * see if the block we need is already in memory. + * note: this lookaside cache has about 10% hit rate. + */ + if (pagb != db->pagbno) { +/* + * note: here, we assume a "hole" is read as 0s. + * if not, must zero pagbuf first. + */ + if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0 + || read(db->pagf, db->pagbuf, PBLKSIZ) < 0) + return 0; + if (!chkpage(db->pagbuf)) + return 0; + db->pagbno = pagb; + + debug(("pag read: %d\n", pagb)); + } + return 1; +} + +static int +getdbit(db, dbit) +register DBM *db; +register long dbit; +{ + register long c; + register long dirb; + + c = dbit / BYTESIZ; + dirb = c / DBLKSIZ; + + if (dirb != db->dirbno) { + if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 + || read(db->dirf, db->dirbuf, DBLKSIZ) < 0) + return 0; + db->dirbno = dirb; + + debug(("dir read: %d\n", dirb)); + } + + return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ); +} + +static int +setdbit(db, dbit) +register DBM *db; +register long dbit; +{ + register long c; + register long dirb; + + c = dbit / BYTESIZ; + dirb = c / DBLKSIZ; + + if (dirb != db->dirbno) { + if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 + || read(db->dirf, db->dirbuf, DBLKSIZ) < 0) + return 0; + db->dirbno = dirb; + + debug(("dir read: %d\n", dirb)); + } + + db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ); + + if (dbit >= db->maxbno) + db->maxbno += DBLKSIZ * BYTESIZ; + + if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 + || write(db->dirf, db->dirbuf, DBLKSIZ) < 0) + return 0; + + return 1; +} + +/* + * getnext - get the next key in the page, and if done with + * the page, try the next page in sequence + */ +static datum +getnext(db) +register DBM *db; +{ + datum key; + + for (;;) { + db->keyptr++; + key = getnkey(db->pagbuf, db->keyptr); + if (key.dptr != NULL) + return key; +/* + * we either run out, or there is nothing on this page.. + * try the next one... If we lost our position on the + * file, we will have to seek. + */ + db->keyptr = 0; + if (db->pagbno != db->blkptr++) + if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0) + break; + db->pagbno = db->blkptr; + if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0) + break; + if (!chkpage(db->pagbuf)) + break; + } + + return ioerr(db), nullitem; +} + diff --git a/ext/SDBM_File/sdbm/sdbm.h b/ext/SDBM_File/sdbm/sdbm.h new file mode 100644 index 0000000000..927e2c2e30 --- /dev/null +++ b/ext/SDBM_File/sdbm/sdbm.h @@ -0,0 +1,234 @@ +/* + * sdbm - ndbm work-alike hashed database library + * based on Per-Ake Larson's Dynamic Hashing algorithms. BIT 18 (1978). + * author: oz@nexus.yorku.ca + * status: public domain. + */ +#define DBLKSIZ 4096 +#define PBLKSIZ 1024 +#define PAIRMAX 1008 /* arbitrary on PBLKSIZ-N */ +#define SPLTMAX 10 /* maximum allowed splits */ + /* for a single insertion */ +#define DIRFEXT ".dir" +#define PAGFEXT ".pag" + +typedef struct { + int dirf; /* directory file descriptor */ + int pagf; /* page file descriptor */ + int flags; /* status/error flags, see below */ + long maxbno; /* size of dirfile in bits */ + long curbit; /* current bit number */ + long hmask; /* current hash mask */ + long blkptr; /* current block for nextkey */ + int keyptr; /* current key for nextkey */ + long blkno; /* current page to read/write */ + long pagbno; /* current page in pagbuf */ + char pagbuf[PBLKSIZ]; /* page file block buffer */ + long dirbno; /* current block in dirbuf */ + char dirbuf[DBLKSIZ]; /* directory file block buffer */ +} DBM; + +#define DBM_RDONLY 0x1 /* data base open read-only */ +#define DBM_IOERR 0x2 /* data base I/O error */ + +/* + * utility macros + */ +#define sdbm_rdonly(db) ((db)->flags & DBM_RDONLY) +#define sdbm_error(db) ((db)->flags & DBM_IOERR) + +#define sdbm_clearerr(db) ((db)->flags &= ~DBM_IOERR) /* ouch */ + +#define sdbm_dirfno(db) ((db)->dirf) +#define sdbm_pagfno(db) ((db)->pagf) + +typedef struct { + char *dptr; + int dsize; +} datum; + +extern datum nullitem; + +#ifdef __STDC__ +#define proto(p) p +#else +#define proto(p) () +#endif + +/* + * flags to sdbm_store + */ +#define DBM_INSERT 0 +#define DBM_REPLACE 1 + +/* + * ndbm interface + */ +extern DBM *sdbm_open proto((char *, int, int)); +extern void sdbm_close proto((DBM *)); +extern datum sdbm_fetch proto((DBM *, datum)); +extern int sdbm_delete proto((DBM *, datum)); +extern int sdbm_store proto((DBM *, datum, datum, int)); +extern datum sdbm_firstkey proto((DBM *)); +extern datum sdbm_nextkey proto((DBM *)); + +/* + * other + */ +extern DBM *sdbm_prep proto((char *, char *, int, int)); +extern long sdbm_hash proto((char *, int)); + +#ifndef SDBM_ONLY +#define dbm_open sdbm_open; +#define dbm_close sdbm_close; +#define dbm_fetch sdbm_fetch; +#define dbm_store sdbm_store; +#define dbm_delete sdbm_delete; +#define dbm_firstkey sdbm_firstkey; +#define dbm_nextkey sdbm_nextkey; +#define dbm_error sdbm_error; +#define dbm_clearerr sdbm_clearerr; +#endif + +/* Most of the following is stolen from perl.h. */ +#ifndef H_PERL /* Include guard */ + +/* + * The following contortions are brought to you on behalf of all the + * standards, semi-standards, de facto standards, not-so-de-facto standards + * of the world, as well as all the other botches anyone ever thought of. + * The basic theory is that if we work hard enough here, the rest of the + * code can be a lot prettier. Well, so much for theory. Sorry, Henry... + */ + +#include <errno.h> +#ifdef HAS_SOCKET +# ifdef I_NET_ERRNO +# include <net/errno.h> +# endif +#endif + +#ifdef MYMALLOC +# ifdef HIDEMYMALLOC +# define malloc Mymalloc +# define realloc Myremalloc +# define free Myfree +# endif +# define safemalloc malloc +# define saferealloc realloc +# define safefree free +#endif + +#if defined(__STDC__) || defined(_AIX) || defined(__stdc__) || defined(__cplusplus) +# define STANDARD_C 1 +#endif + +#include <stdio.h> +#include <ctype.h> +#include <setjmp.h> + +#ifdef I_UNISTD +#include <unistd.h> +#endif + +#ifndef MSDOS +# ifdef PARAM_NEEDS_TYPES +# include <sys/types.h> +# endif +# include <sys/param.h> +#endif + +#ifndef _TYPES_ /* If types.h defines this it's easy. */ +# ifndef major /* Does everyone's types.h define this? */ +# include <sys/types.h> +# endif +#endif + +#include <sys/stat.h> + +#ifndef SEEK_SET +# ifdef L_SET +# define SEEK_SET L_SET +# else +# define SEEK_SET 0 /* Wild guess. */ +# endif +#endif + +/* Use all the "standard" definitions? */ +#ifdef STANDARD_C +# include <stdlib.h> +#endif /* STANDARD_C */ + +#define MEM_SIZE Size_t + +#ifdef I_STRING +#include <string.h> +#else +#include <strings.h> +#endif + +#ifdef I_MEMORY +#include <memory.h> +#endif + +#if defined(mips) && defined(ultrix) && !defined(__STDC__) +# undef HAS_MEMCMP +#endif + +#ifdef HAS_MEMCPY +# if !defined(STANDARD_C) && !defined(I_STRING) && !defined(I_MEMORY) +# ifndef memcpy + extern char * memcpy _((char*, char*, int)); +# endif +# endif +#else +# ifndef memcpy +# ifdef HAS_BCOPY +# define memcpy(d,s,l) bcopy(s,d,l) +# else +# define memcpy(d,s,l) my_bcopy(s,d,l) +# endif +# endif +#endif /* HAS_MEMCPY */ + +#ifdef HAS_MEMSET +# if !defined(STANDARD_C) && !defined(I_STRING) && !defined(I_MEMORY) +# ifndef memset + extern char *memset _((char*, int, int)); +# endif +# endif +# define memzero(d,l) memset(d,0,l) +#else +# ifndef memzero +# ifdef HAS_BZERO +# define memzero(d,l) bzero(d,l) +# else +# define memzero(d,l) my_bzero(d,l) +# endif +# endif +#endif /* HAS_MEMSET */ + +#ifdef HAS_MEMCMP +# if !defined(STANDARD_C) && !defined(I_STRING) && !defined(I_MEMORY) +# ifndef memcmp + extern int memcmp _((char*, char*, int)); +# endif +# endif +#else +# ifndef memcmp +# define memcmp(s1,s2,l) my_memcmp(s1,s2,l) +# endif +#endif /* HAS_MEMCMP */ + +/* we prefer bcmp slightly for comparisons that don't care about ordering */ +#ifndef HAS_BCMP +# ifndef bcmp +# define bcmp(s1,s2,l) memcmp(s1,s2,l) +# endif +#endif /* HAS_BCMP */ + +#ifdef I_NETINET_IN +# include <netinet/in.h> +#endif + +#endif /* Include guard */ diff --git a/ext/SDBM_File/sdbm/tune.h b/ext/SDBM_File/sdbm/tune.h new file mode 100644 index 0000000000..b95c8c8634 --- /dev/null +++ b/ext/SDBM_File/sdbm/tune.h @@ -0,0 +1,23 @@ +/* + * sdbm - ndbm work-alike hashed database library + * tuning and portability constructs [not nearly enough] + * author: oz@nexus.yorku.ca + */ + +#define BYTESIZ 8 + +/* + * important tuning parms (hah) + */ + +#define SEEDUPS /* always detect duplicates */ +#define BADMESS /* generate a message for worst case: + cannot make room after SPLTMAX splits */ +/* + * misc + */ +#ifdef DEBUG +#define debug(x) printf x +#else +#define debug(x) +#endif diff --git a/ext/SDBM_File/sdbm/util.c b/ext/SDBM_File/sdbm/util.c new file mode 100644 index 0000000000..4b03d89f09 --- /dev/null +++ b/ext/SDBM_File/sdbm/util.c @@ -0,0 +1,50 @@ +#include <stdio.h> +#ifdef SDBM +#include "sdbm.h" +#else +#include "ndbm.h" +#endif + +void +oops(s1, s2) +register char *s1; +register char *s2; +{ + extern int errno, sys_nerr; + extern char *sys_errlist[]; + extern char *progname; + + if (progname) + fprintf(stderr, "%s: ", progname); + fprintf(stderr, s1, s2); + if (errno > 0 && errno < sys_nerr) + fprintf(stderr, " (%s)", sys_errlist[errno]); + fprintf(stderr, "\n"); + exit(1); +} + +int +okpage(pag) +char *pag; +{ + register unsigned n; + register off; + register short *ino = (short *) pag; + + if ((n = ino[0]) > PBLKSIZ / sizeof(short)) + return 0; + + if (!n) + return 1; + + off = PBLKSIZ; + for (ino++; n; ino += 2) { + if (ino[0] > off || ino[1] > off || + ino[1] > ino[0]) + return 0; + off = ino[1]; + n -= 2; + } + + return 1; +} |