Path: utzoo!attcan!uunet!husc6!purdue!umd5!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.sources.d
Subject: Re: Problem with Spacewar under Sys V, dbm.h
Message-ID: <11960@mimsy.UUCP>
Date: 14 Jun 88 12:21:15 GMT
References: <937@fig.bbn.com>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 64

In article <937@fig.bbn.com> rsalz@bbn.com (Rich Salz) writes:
>Okay, fact time.

... or is it ... fact-OID?? :-)

>... The DBM library was present in Version 7; for some reason
>ATT dropped it; nobody seems to know why.  UCB kept it, and improved it to
>handle multiple open files, etc.

It may have been one of those things added after the V6/PWB/USG
line split away from the V6/V7/32V line.

>Rumor has it that a combination of Chris Torek and James Gosling wrote and
>modified a replacement DBM package that Gosling used for the documentation
>subsystem that is in the Emacs he wrote while at CMU.  Unipress has a
>product based on this "Gosmacs."  I'd love to hear the facts of the
>situation.

That is some rumour!  jag (that is `James A Gosling': his login id)
took the V7 dbm and modified it in three ways:  First, to support more
than one database; second, to store just one `long' (well, actually
two, offset+size) under each key (as part of the key itself); and
third, to use a third file to store the actual data (now arbitrarily
long, since the `datum' for a given key no longer had to fit in a dbm
block).

Some time after reading jag's version and making two `ndbm's (similar
to the 4.3BSD version, but we were running 4.2BSD/BRL at the time) I
came up with a method of making individual database items serve as both
key and datum as appropriate; I wrote this `multi-keyed dbm' without
looking at the V7 dbm code again, except for the hash function which I
stole outright (as, I believe, did jag).  (By then I had it practically
memorised anyway, so who knows whether that means anything.)  At any
rate, I posted mine, and had it available for anonymous FTP, but after
some footwork by John Gilmore I removed it from general access, as
AT&T's reply as to whether it was free of their stuff was something
like `maybe, but if we decide we care we might sue anyway'.

(Not that dbm is at all suited to a general purpose database.  It
does not even have any locking...!)

I am not sure that I ever did anything to jag's Emacs ndbm code, aside
from possible portability changes (making Emacs run on a Pyramid
exposed numerous Vaxisms).

>The key to the DBM package is the clever hashing and block splitting scheme
>it uses in maintaining its index files.

Well, the hashing scheme anyway, and what goes in the `access' routine
(where the mask, and from that, the block number, is computed).  The
split scheme follows directly from this.  (See my recent followup in
comp.unix.questions.)  The iteration code (which I did not describe)
also follows, but only in a devious way (you run down the left side of
the node tree, then do a depth first traversal using knowledge as to
how the masks work).

>Several years ago someone in the UCLA Locus project posted a summary of
>how the DBM package does its work.

I never saw that one, but I think my last followup was my third
description of the hashing scheme.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris