perl 5.000perl-5.000

[editor's note: this commit combines approximate 4 months of furious
releases of Andy Dougherty and Larry Wall - see pod/perlhist.pod for
details.  Andy notes that;
 
Alas neither my "Irwin AccuTrack" nor my DC 600A quarter-inch cartridge 
backup tapes from that era seem to be readable anymore.  I guess 13 years 
exceeds the shelf life for that backup technology :-(.
]

30 files changed, 6268 insertions, 0 deletions

diff --git a/ext/SDBM_File/Makefile.SH b/ext/SDBM_File/Makefile.SH
new file mode 100644
index 0000000000..1f181e3b09
--- /dev/null
+++ b/ext/SDBM_File/Makefile.SH
@@ -0,0 +1,216 @@
+: 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
+
+: Find out directory name.  This is also the extension name.
+ext=`pwd | $sed -e 's@.*/@@'`
+
+: This extension might have its own typemap
+if test -f typemap; then
+	exttypemap='typemap'
+else
+	exttypemap=''
+fi
+
+: This extension might need additional libraries.
+potential_libs=" "
+. $TOP/ext/util/extliblist
+
+: This extension might need bootstrap support
+if test -f ${ext}_BS; then
+	bootdep=${ext}_BS
+else
+	bootdep=''
+fi
+
+case "$dlsrc" in
+dl_aix*)
+    echo "#!" > $ext.exp
+    echo "boot_$ext" >> $ext.exp
+    ;;
+esac
+
+echo "Extracting ext/$ext/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 $ext extension to perl.
+# 
+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}
+
+EXT = $ext
+
+# $ext might have its own typemap
+EXTTYPEMAP = $exttypemap
+
+# $ext might have its own bootstrap support
+BOOTDEP  = $bootdep
+BOOTSTRAP  = $ext.bs
+
+# The following are used to build and install shared libraries for
+# dynamic loading.
+LDDLFLAGS = $lddlflags
+CCDLFLAGS = $ccdlflags
+CCCDLFLAGS = $cccdlflags
+SO = $so
+DLEXT = $dlext
+
+# $ext might need to be linked with some extra libraries.
+# EXTRALIBS =  full list of libraries needed for static linking.
+#		Only those libraries that actually exist are included.
+# DYNLOADLIBS = list of those libraries that are needed but can be
+#		linked in dynamically on this platform.  On SunOS, for
+#		example, this would be .so* libraries, but not archive
+#		libraries.  The bootstrap file is installed only if
+#		this list is not empty.
+# STATLOADLIBS = list of those libraries which must be statically
+#		linked into the shared library.  On SunOS 4.1.3, 
+#		for example,  I have only an archive version of
+#		-lm, and it must be linked in statically.
+EXTRALIBS = $extralibs
+DYNALOADLIBS  = $dynaloadlibs
+STATLOADLIBS = $statloadlibs
+
+!GROK!THIS!
+
+$spitshell >>Makefile <<'!NO!SUBS!'
+
+# Where to put things:
+AUTO = $(TOP)/lib/auto
+INSTALLBOOT = $(AUTO)/$(EXT)/$(EXT).bs
+INSTALLDYNAMIC = $(AUTO)/$(EXT)/$(EXT).$(DLEXT)
+INSTALLSTATIC = $(EXT).a
+INSTALLPM = $(TOP)/lib/$(EXT).pm
+
+PERL = $(ABSTOP)/miniperl
+XSUBPP = $(TOP)/ext/xsubpp
+SHELL = /bin/sh
+CCCMD = `sh $(shellflags) $(TOP)/cflags $@`
+
+.c.o:
+	$(CCCMD) $(CCCDLFLAGS) -I$(TOP) $*.c
+
+all:	dynamic
+# Phony target to force checking subdirectories.
+FORCE:
+
+config:
+
+# Target for Dynamic Loading:
+dynamic:	$(INSTALLDYNAMIC) $(INSTALLPM) $(INSTALLBOOT)
+
+$(INSTALLDYNAMIC): $(EXT).o sdbm/libsdbm.a
+	@test -d $(AUTO) || mkdir $(AUTO)
+	@test -d $(AUTO)/$(EXT) || mkdir $(AUTO)/$(EXT)
+	ld $(LDDLFLAGS) -o $@ $(EXT).o sdbm/libsdbm.a $(STATLOADLIBS)
+
+$(BOOTSTRAP):	Makefile $(BOOTDEP)
+	$(PERL) -I$(TOP)/lib $(TOP)/ext/util/mkbootstrap $(DYNALOADLIBS)
+	touch $(BOOTSTRAP)
+
+$(INSTALLBOOT):	$(BOOTSTRAP)
+	@test ! -s $(BOOTSTRAP) || cp $(BOOTSTRAP) $@
+
+# Target for Static Loading:
+static: $(INSTALLSTATIC) $(INSTALLPM)
+
+$(INSTALLSTATIC):	$(EXT).o sdbm/libsdbm.a
+	cp sdbm/libsdbm.a $@
+	ar r $@ $(EXT).o
+	$(RANLIB) $@
+	echo $(EXTRALIBS) >> $(TOP)/ext.libs
+
+$(EXT).c:	$(EXT).xs $(XSUBPP) $(TOP)/ext/typemap $(EXTTYPEMAP) $(TOP)/cflags Makefile
+	$(PERL) $(XSUBPP) $(EXT).xs >tmp
+	mv tmp $@
+
+sdbm/libsdbm.a:	FORCE
+	@cd sdbm;  \
+	if test ! -f Makefile ; then \
+	test -f Makefile.SH && sh Makefile.SH ; \
+	fi ; 	$(MAKE)
+
+$(INSTALLPM):	$(EXT).pm
+	rm -f $@
+	cp $(EXT).pm $@
+	cd $(TOP); $(PERL) autosplit $(EXT)
+
+clean:
+	-cd sdbm; $(MAKE) clean
+	rm -f *.o *.a mon.out core $(EXT).c so_locations $(BOOTSTRAP) $(EXT).exp
+
+realclean: 	clean
+	-cd sdbm; $(MAKE) realclean
+	rm -f makefile Makefile
+	rm -f $(INSTALLPM) $(INSTALLDYNAMIC) $(INSTALLSTATIC) $(INSTALLBOOT)
+	rm -rf $(AUTO)/$(EXT)
+
+purge:	realclean
+
+$(EXT).o :	$(TOP)/EXTERN.h
+$(EXT).o :	$(TOP)/perl.h
+$(EXT).o :	$(TOP)/embed.h
+$(EXT).o :	$(TOP)/config.h
+$(EXT).o :	$(TOP)/unixish.h
+$(EXT).o :	$(TOP)/handy.h
+$(EXT).o :	$(TOP)/regexp.h
+$(EXT).o :	$(TOP)/sv.h
+$(EXT).o :	$(TOP)/util.h
+$(EXT).o :	$(TOP)/form.h
+$(EXT).o :	$(TOP)/gv.h
+$(EXT).o :	$(TOP)/cv.h
+$(EXT).o :	$(TOP)/opcode.h
+$(EXT).o :	$(TOP)/op.h
+$(EXT).o :	$(TOP)/cop.h
+$(EXT).o :	$(TOP)/av.h
+$(EXT).o :	$(TOP)/hv.h
+$(EXT).o :	$(TOP)/mg.h
+$(EXT).o :	$(TOP)/scope.h
+$(EXT).o :	$(TOP)/pp.h
+$(EXT).o :	$(TOP)/proto.h
+$(EXT).o :	$(TOP)/XSUB.h 
+
+Makefile:	Makefile.SH $(TOP)/config.sh ; /bin/sh Makefile.SH
+$(TOP)/config.h:	$(TOP)/config.sh; cd $(TOP); /bin/sh config_h.SH
+$(TOP)/embed.h:	$(TOP)/config.sh; cd $(TOP); /bin/sh embed_h.SH
+$(TOP)/cflags:	$(TOP)/config.sh; cd $(TOP); /bin/sh cflags.SH
+
+!NO!SUBS!
+chmod 644 Makefile
+$eunicefix Makefile
+
diff --git a/ext/SDBM_File/SDBM_File.pm b/ext/SDBM_File/SDBM_File.pm
new file mode 100644
index 0000000000..1f93e52893
--- /dev/null
+++ b/ext/SDBM_File/SDBM_File.pm
@@ -0,0 +1,11 @@
+package SDBM_File;
+
+require TieHash;
+require DynaLoader;
+@ISA = qw(TieHash DynaLoader);
+
+bootstrap SDBM_File;
+
+1;
+
+__END__
diff --git a/ext/SDBM_File/SDBM_File.xs b/ext/SDBM_File/SDBM_File.xs
new file mode 100644
index 0000000000..97f9c1f9f4
--- /dev/null
+++ b/ext/SDBM_File/SDBM_File.xs
@@ -0,0 +1,71 @@
+#include "EXTERN.h"
+#include "perl.h"
+#include "XSUB.h"
+#include "sdbm/sdbm.h"
+
+typedef DBM* SDBM_File;
+#define sdbm_TIEHASH(dbtype,filename,flags,mode) sdbm_open(filename,flags,mode)
+#define sdbm_FETCH(db,key)			sdbm_fetch(db,key)
+#define sdbm_STORE(db,key,value,flags)		sdbm_store(db,key,value,flags)
+#define sdbm_DELETE(db,key)			sdbm_delete(db,key)
+#define sdbm_FIRSTKEY(db)			sdbm_firstkey(db)
+#define sdbm_NEXTKEY(db,key)			sdbm_nextkey(db)
+
+
+MODULE = SDBM_File	PACKAGE = SDBM_File	PREFIX = sdbm_
+
+SDBM_File
+sdbm_TIEHASH(dbtype, filename, flags, mode)
+	char *		dbtype
+	char *		filename
+	int		flags
+	int		mode
+
+void
+sdbm_DESTROY(db)
+	SDBM_File	db
+	CODE:
+	sdbm_close(db);
+
+datum
+sdbm_FETCH(db, key)
+	SDBM_File	db
+	datum		key
+
+int
+sdbm_STORE(db, key, value, flags = DBM_REPLACE)
+	SDBM_File	db
+	datum		key
+	datum		value
+	int		flags
+    CLEANUP:
+	if (RETVAL) {
+	    if (RETVAL < 0 && errno == EPERM)
+		croak("No write permission to sdbm file");
+	    warn("sdbm store returned %d, errno %d, key \"%s\"",
+			RETVAL,errno,key.dptr);
+	    sdbm_clearerr(db);
+	}
+
+int
+sdbm_DELETE(db, key)
+	SDBM_File	db
+	datum		key
+
+datum
+sdbm_FIRSTKEY(db)
+	SDBM_File	db
+
+datum
+sdbm_NEXTKEY(db, key)
+	SDBM_File	db
+	datum		key
+
+int
+sdbm_error(db)
+	SDBM_File	db
+
+int
+sdbm_clearerr(db)
+	SDBM_File	db
+
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;
+}
diff --git a/ext/SDBM_File/typemap b/ext/SDBM_File/typemap
new file mode 100644
index 0000000000..a6b0e5faa8
--- /dev/null
+++ b/ext/SDBM_File/typemap
@@ -0,0 +1,25 @@
+#
+#################################### DBM SECTION
+#
+
+datum			T_DATUM
+gdatum			T_GDATUM
+NDBM_File		T_PTROBJ
+GDBM_File		T_PTROBJ
+SDBM_File		T_PTROBJ
+ODBM_File		T_PTROBJ
+DB_File			T_PTROBJ
+DBZ_File		T_PTROBJ
+FATALFUNC		T_OPAQUEPTR
+
+INPUT
+T_DATUM
+	$var.dptr = SvPV($arg, na);
+	$var.dsize = (int)na;
+T_GDATUM
+	UNIMPLEMENTED
+OUTPUT
+T_DATUM
+	sv_setpvn($arg, $var.dptr, $var.dsize);
+T_GDATUM
+	sv_usepvn($arg, $var.dptr, $var.dsize);